Dichotomy for Graph Homomorphisms with Complex Values on Bounded Degree Graphs
Explore a comprehensive analysis of graph homomorphisms with complex values on bounded degree graphs in this 25-minute IEEE conference talk. Delve into the intricacies of partition functions, vertex weights, and the ease model as presented by Jin-Yi Cai and Artsiom Hovarau from the University of Wisconsin-Madison. Examine the complex theory behind dichotomy and generating sets, and understand the purification structure and thickening edge gadgets. Investigate the multiplicatively broken one matrix and non-multiplicative block requirements through the Vandermonde argument. Learn about the contrapositive case gadgets, vendor mode, and exponential polynomial transfer procedure. Follow the outline of the main proof, including meta arguments and constructivity, to gain a deeper understanding of this advanced topic in graph theory and computational complexity.