arXiv preprint ·
Near linear mixing of random-cluster Glauber dynamics on random regular graphs
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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 \in (0,1)$ and a clustering weight $q \in [1,\infty)$, 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_{\mathsf 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_{\mathsf s}(q,d)$, where $p_{\mathsf 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_{\mathsf s}$. For comparison, the best prior sampling results for these models that held for all $p>p_{\mathsf s}$ required $q\gtrsim \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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Probability
Low-Temperature Sampling via Equilibrium Disagreements
Functional inequalities from the fundamental limits of Bayesian estimation
Tusnády's problem and online two-sample thinning
Can a self-sustaining chemical network emerge due to just a few catalysts?
CARM: Conformal Adaptive Risk Masking for Reliable Scientific Super-Resolution
Get the few papers worth your time in Probability every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.