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.