Sampling From the Random Cluster Model at All Temperatures on Random Graphs

on YouTube ↗34m

" summary

For random d‑regular graphs with d ≥ 5 and q at least about d^d, there are polynomial‑time algorithms that approximately count and sample the Potts and random‑cluster measures at every inverse temperature (subcritical, supercritical and critical). The proof rewrites each phase as a polymer model and proves convergent cluster expansion bounds using expansion properties to show configurations have >90% or <10% of edges w.h.p.; consequences include analytic free energy off criticality, exponential decay of correlations, local weak convergence to free/wired tree measures, and an explicit limiting distribution at criticality determined by small cycle counts.

AI-written summary · about

" chapters (13)

1. 0:00Introduction
2. 1:10Background
3. 2:10Models
4. 3:50Random Cluster Partition
5. 4:47Approximate Counting and Sampling
6. 6:06General Comments
7. 8:01Random Graphs
8. 9:54Results
9. 14:11Algorithms
10. 15:50Techniques
11. 16:41Three Steps
12. 20:34Consequence
13. 21:27Open Questions

" related talks

• 35mOn the Chromatic Number of Random Regular GraphsSamuel Hetterich · Random Instances and Phase Transitions (Simons Institute, 2016)
• 44mAlgorithmic Pirogov-Sinai TheoryTyler Helmuth · Deterministic Counting, Probability, and Zeros of Partition Functions (Simons Institute workshop, 2019)
• 25mLucky Talk: From Coding to ClusteringEmmanuel Abbe · Information Theory, Learning and Big Data (Simons Institute, 2015)
• 54mNegative Dependence and Lorentzian PolynomialsPetter Brändén · Deterministic Counting, Probability, and Zeros of Partition Functions (Simons Institute workshop, 2019)
• 42mBootstrap Percolation on Random GraphsMihyun Kang · Random Instances and Phase Transitions (Simons Institute, 2016)
• 35mContagious Sets in Random GraphsDaniel Reichman · Random Instances and Phase Transitions (Simons Institute, 2016)
• 01h 04mHigher-dimensional Expansion of Random Geometric ComplexesTselil Schramm · Structural Results 2023
• 46mPhase Transitions in Random CSPsNike Sun · Random Instances and Phase Transitions (Simons Institute, 2016)