Near linear mixing of random-cluster Glauber dynamics on random regular graphs
Abstract
We study the random-cluster model on locally treelike graphs at low temperatures. This is a model of dependent percolation parametrized by an edge probability p ∈ (0,1) and a clustering weight q ∈ [1,∞), generalizing independent Bernoulli percolation (q=1) and closely related to the classical ferromagnetic Ising and Potts spin systems at integer q. For q>2, at parameter p below the tree uniqueness threshold pu(q,d), it is expected that sampling is easy and local Markov chains mix rapidly on all graphs with degree bounded by d. On typical graphs, the same is predicted at p>ps(q,d), where ps(q,d) is a second uniqueness transition point on the d-regular wired tree. Our result confirms this prediction for random regular graphs, showing that the random-cluster Glauber dynamics mix in time O(n1+o(1)) on a random d-regular graph for all fixed q>2 and p>ps. For comparison, the best prior sampling results for these models that held for all p>ps required q≳ log d \cite{BGPZ26}. The key difficulty is that simply utilizing the contraction of cavity messages on d-regular trees does not suffice to cover the entire regime q>2. To address this issue, motivated by \cite{LS26}, we develop a careful bootstrap argument to show the shrinkage of disagreement under grand coupling. The core ideas of the proof were generated using GPT-6 and the Pharos system; the proof was then refined and simplified by the author.
Related
- Glauber Dynamics for Sampling Colorings: Rapid Mixing above (1+1/e)Δ via Hidden Hard-Core Models
- Mixing profile for Glauber dynamics of the discrete Gaussian Free Field starting from super-harmonic functions
- Optimal Mixing of Glauber Dynamics for the Sherrington-Kirkpatrick Model at β< 1/2
- Rank-1-perturbed trickledown theorems: Mixing time of Glauber dynamics for the Sherrington-Kirkpatrick model up to β≤ 1/2+ε
- Rapid mixing of Potts Glauber dynamics throughout uniqueness
BibTeX
@misc{li2026near,
title = {{Near linear mixing of random-cluster Glauber dynamics on random regular graphs}},
author = {Zhangsong Li},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.05794},
eprint = {2611.05794},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.05794},
}
RIS
TY - UNPB
TI - Near linear mixing of random-cluster Glauber dynamics on random regular graphs
AU - Zhangsong Li
PY - 2026
DA - 2026/11/04
PB - arXiv
DO - 10.48550/arxiv.2611.05794
UR - https://arxiv.org/abs/2611.05794
AB - We study the random-cluster model on locally treelike graphs at low temperatures. This is a model of dependent percolation parametrized by an edge probability p ∈ (0,1) and a clustering weight q ∈ [1,∞), generalizing independent Bernoulli percolation (q=1) and closely related to the classical ferromagnetic Ising and Potts spin systems at integer q. For q>2, at parameter p below the tree uniqueness threshold p_u(q,d), it is expected that sampling is easy and local Markov chains mix rapidly on all graphs with degree bounded by d. On typical graphs, the same is predicted at p>p_s(q,d), where p_s(q,d) is a second uniqueness transition point on the d-regular wired tree. Our result confirms this prediction for random regular graphs, showing that the random-cluster Glauber dynamics mix in time O(n^1+o(1)) on a random d-regular graph for all fixed q>2 and p>p_s. For comparison, the best prior sampling results for these models that held for all p>p_s required q≳ log d \cite{BGPZ26}. The key difficulty is that simply utilizing the contraction of cavity messages on d-regular trees does not suffice to cover the entire regime q>2. To address this issue, motivated by \cite{LS26}, we develop a careful bootstrap argument to show the shrinkage of disagreement under grand coupling. The core ideas of the proof were generated using GPT-6 and the Pharos system; the proof was then refined and simplified by the author.
ER -