Talks

Spring 2016

# Counting Matrix Partitions of Graphs

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

Speaker:

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.

Attachment | Size |
---|---|

Counting Matrix Partitions of Graphs | 469.38 KB |