Abstract
Each symmetric matrix A defines a graph homomorphism function Z_A on undirected graphs. The function Z_A is also called the partition function from statistical physics, and can encode many interesting graph properties including counting vertex covers and k-colorings. During the past fifteen years, a sequence of (explicit) dichotomy theorems have been established for Z_A over 0-1 valued matrices [Dyer and Greenhill], nonnegative matrices [Bulatov and Grohe], real matrices [Goldberg, Grohe, Jerrum and Thurley], and complex matrices [Cai, Chen and Lu]. In this lecture we will review the complexity classification of Z_A behind these dichotomies, and showcase some of the techniques developed in these works.
The complexity of counting graph homomorphisms, Dyer and Greenhill
http://onlinelibrary.wiley.
The complexity of partition functions, Bulatov and Grohe
http://www.sciencedirect.com/
A complexity dichotomy for partition functions with mixed signs, Goldberg, Grohe, Jerrum and Thurley
http://epubs.siam.org/doi/abs/
Graph homomorphisms with complex values: A dichotomy theorem, Cai, Chen and Lu
http://epubs.siam.org/doi/abs/
The second session of this mini course will take place on Wednesday, January 27 from 1:30 pm – 2:30 pm.