Approximately Counting Graph Homomorphisms
summary
Fixing any nontrivial template H, approximately counting H‑colorings is never easier than approximately counting independent sets in bipartite graphs: the result shows approximate counting ≥ BIS for every connected nontrivial component. The proof uses an inductive reduction that builds gadgets nonconstructively (via Lovász distinguishing gadget arguments) to force specific color choices, and handles multiple max‑degree types by gluing many copies of a distinguishing graph J. Classification remains incomplete (simple four‑vertex H can be unresolved).
AI-written summary · about
chapters (10)
- 0:00Intro
- 3:09The H-Colouring Decision Problem
- 6:22The H-Colouring Counting Problem
- 11:25Warm-up: connected 3-vertex H
- 17:47No life below #BIS... detour into complexity of sampling
- 22:20Disconnected H
- 27:19Proof overview
- 36:58A First Attempt - Multiple vertices with Max Degree
- 38:20The Sampling World - Gluing Reductions
- 42:42Tools from Graph Homomorphisms
related talks
58mHomomorphism Indistinguishability
18mCompleteness of an Axiomatization of Graph Isomorphism via Graph Rewriting in Coq
20mCounting and Sampling Perfect Matchings in Regular Expanding Non-Bipartite Graphs
01h 22mTutorial 3: Geometric Invariant Theory
01h 19mTutorial 2: Algorithmic Invariant Theory
25mCubical Synthetic Homotopy Theory
32mA Finite Alternation Result for Reversible Boolean Circuits
21mMax-3-Lin over Non-Abelian Groups with Universal Factor Graphs