Title: Graph Homomorphisms with Complex Values: A Dichotomy Theorem
Speaker: Xi Chen, Rutgers University
Date: Wednesday, November 26, 2008 11:00-12:00pm
Location: CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
The graph homomorphism problem has been studied intensively. Given an m by m symmetric matrix A, the graph homomorphism function is defined as Z_A(G) = \sum_{f:V \rightarrow [m]} \prod_{(u,v) \in E} A_{f(u),f(v)}, where G = (V,E) is any undirected graph. The function Z_A(G) can encode many interesting graph properties, including counting vertex covers and k-colorings. We study the computational complexity of Z_A(G) for arbitrary complex valued matrices A. Building on work by Dyer and Greenhill, Bulatov and Grohe, and especially the recent beautiful work by Goldberg, Grohe, Jerrum and Thurley, we prove a complete dichotomy theorem for this problem.
Joint work with Jin-Yi Cai and Pinyan Lu.