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.

Introduction
Graph homomorphism
Partition function
Vertex weights
Partition functions
Ease model
Other similar models
Complex theory
Dichotomy
Generating Sets
Purification
Structure
Thickening
Edge Gadgets
Multiplicatively Broken One
Matrix
Nonmultiplicative Block Requirements
Vandermot Argument
Contrapositive
Case gadgets
Replace every vertex
Vendor mode
Exponential polynomial
Transfer procedure
Outline main proof
Example of meta argument
Strengthens
Constructivity