Siegel's Theorem, Edge Coloring, and a Holant Dichotomy
summary
Proves that for every kappa ≥ 3 the problem of counting proper k-edge‑colorings on k‑regular graphs is #P‑complete, by reducing a Tutte/top‑polynomial evaluation on medial graphs to edge‑coloring. Key tools are holographic transformations and spectral interpolation of a 5×5 recurrence matrix, plus number‑theory inputs: a lattice‑condition on eigenvalues checked via Galois theory and an application of Siegel's theorem (Puiseux expansion argument) to rule out extraneous integer solutions needed for the interpolation.
AI-written summary · about
chapters (23)
- 0:00Intro
- 1:42Diophantine Equations with Enormous Solutions Pell's Equation (genus 0)
- 3:14Edge Coloring-Decision Problem
- 6:28Edge Coloring-Counting Problem
- 8:25Three Frameworks for Counting Problems
- 11:25Constraint Functions
- 14:54Equivalence with sl(2:C) representation
- 16:49Another representation
- 20:31#x-EdgeColoring as a Holant Problem
- 26:01Examples of Graph Homomorphism
- 30:26Dichotomy Theorem for Graph Homomorphism
- 33:49Non-trivial Examples of Tractable Holant Problems
- 37:20Tutte Polynomial
- 39:03Eulerian Subgraphs
- 40:15Eulerian Local Configuration
- 40:44The Eulerian Signature
- 41:34An Arity 4 Gadget
- 42:07#P-hardness of EdgeColoring
- 43:44An Interpolation
- 45:47Overview of Proof of Dichotomy Holant(G:f)
- 46:22Lattice Condition
- 49:31Effective Siegel's Theorem?
- 50:27Puiseux Series
related talks
01h 02mFine-Grained Counting Complexity II
29mColor Coding-Related Techniques
06mThe 5 Colour Theorem
01h 02mFine-Grained Counting Complexity I
01h 00mCorrespondence Colouring of Random Graphs
19mA Formal Disproof of Hirsch Conjecture
41mOn counting subgraphs and why counting seeds makes more sense (if one thinks about it clearly)
33mLower Bounds for Subexponential Parameterized Complexity of Minimum Fill-in and Related Problems