Counting Independent Sets and Colorings on Almost Every Random Regular Bipartite Graph
Talkat Deterministic Counting, Probability, and Zeros of Partition Functions (Simons Institute workshop, 2019) · 2019-03-18..03-22
summary
Shows a deterministic FPTAS for counting independent sets and q‑colorings on almost every random Δ‑regular bipartite graph when Δ is sufficiently large (Δ is a growing function of q or the activity λ, e.g. proofs require Δ beyond a concrete threshold like around 50). Uses an explicit polymer model built from ground‑state clusters and their neighborhoods, proves the neighborhoods cover nearly all configurations, establishes exponential weight decay and a Kotecký–Preiss verification, and converts the polymer partition function into an efficient approximate count.
AI-written summary · about
chapters (13)
- 0:00Intro
- 1:36The common recipe
- 3:19Random Regular Bipartite Graphs
- 10:59Define a polymer model for IL
- 14:54Prove that it is a good approximation
- 15:30Verify KP condition
- 18:15Our Theorems
- 20:19Counting Colorings
- 21:14Identify ground clusters
- 23:12Simple facts
- 23:50Prove that their summation is a good approximation
- 26:17Define a polymer model for Cx
- 31:07Open questions