Abstract
Matrix partitions are a generalization of graph homomorphisms. Given a d-by-d symmetric matrix M with entries from {0,1,*}, an M-partition of a graph G is a partition of its vertices into sets V_1, ..., V_d such that:
- if M[i,j] = 0, there are no edges between V_i and V_j;
- if M[i,j] = 1, then G contains every possible edge between V_i and V_j;
- if M[i,j] = *, there are no restrictions on the edges between V_i and V_j.
Thus, it can be seen that a homomorphism from a G to a graph H corresponds to an M-partition for a matrix M that contains no 1's.
I will discuss a complexity dichotomy for counting list M-partitions, i.e., M-partitions where each vertex of the graph has, in addition, a list of the parts of M in which it may be placed. These problems are #P-complete if M has a structure we call a derectangularizing sequence, and in FP otherwise. I will also briefly discuss work on the problem without lists.
Joint work with Martin Dyer, Andreas Goebel, Leslie Ann Goldberg, Colin McQuillan and Tomo Yamakami.