Counting Hypergraph Colorings in the Local Lemma Regime
Talkat Deterministic Counting, Probability, and Zeros of Partition Functions (Simons Institute workshop, 2019) · 2019-03-18..03-22
summary
Deterministic algorithm gives a polynomial-time deterministic approximation scheme for counting q-colorings of k-uniform hypergraphs in a Local Lemma regime (requires large k and a large constant where q is roughly poly(Delta)^{1/(k-1)}). It uses a refined Moitra-style adaptive coupling tree encoded as a linear program, a truncation that stops in O(log n) depth, and LLL-based local uniformity to bound truncation error (error per marginal ~5/T). The method computes marginals, assembles a partial coloring, and exactly colors small components.
AI-written summary · about
chapters (10)
- 0:00Introduction and motivations
- 1:36Graph coloring background
- 3:33Counting and sampling methods
- 8:18Hypergraph coloring overview
- 12:22Methodological challenges
- 14:47Local Lemma and uniformity
- 20:27Coupling process for counting
- 28:35Linear programming framework
- 37:58Deterministic algorithm summary
- 39:14Future research and questions