Spring 2016

Counting Matrix Partitions of Graphs

Tuesday, March 29th, 2016 3:00 pm3:45 pm

Add to Calendar

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.
PDF icon Counting Matrix Partitions of Graphs469.38 KB