Path Coupling, Metrics, and Sampling Problems in Graphs and Hypergraphs
summary
Uses path coupling with a custom metric chosen by solving a linear program metric to prove rapid mixing of the independent set Markov chain on hypergraphs whenever edge size m ≥ Δ+2 and m ≥ 5, giving O(n log n) mixing and hence an FPRAS for counting in that regime. Introduces stopping times and penalized distances to handle near‑full edges, derives concrete coefficients and thresholds, and contrasts these positive bounds with hardness results (no FPRAS for very large Δ growing like about 2^{m/2}) and alternative correlation‑decay limits.
AI-written summary · about
chapters (17)
- 0:00Intro
- 0:41Counting independent sets in hypergraphs
- 2:38Markov chain: Glauber dynamics
- 8:51Example: independent sets in graphs
- 15:09Path coupling for hypergraphs
- 15:51Intuition for a better analysis
- 18:09Modifying the metric
- 19:34Bad configurations
- 20:26Defining a new metric
- 21:29Transitions changing d
- 23:02The path coupling equation
- 26:29Other work on hypergraph independent sets
- 31:00Colouring hypergraphs
- 34:14Metric approach for m=3
- 35:02The path coupling inequalities
- 36:00Rapid mixing condition
- 36:48Colouring bipartite graphs