Random-cluster dynamics on random regular graphs in tree uniqueness

Abstract

We establish rapid mixing of the random-cluster Glauber dynamics on random $\Delta$-regular graphs for all $q\ge 1$ and $p<p_u(q,\Delta )$, where the threshold $p_u(q,\Delta )$ corresponds to a uniqueness/non-uniqueness phase transition for the random-cluster model on the (infinite) $\Delta$-regular tree. It is expected that this threshold is sharp, and for $q>2$ the Glauber dynamics on random $\Delta$-regular graphs undergoes an exponential slowdown at $p_u(q,\Delta )$. More precisely, we show that for every $q\ge 1$, $\Delta \ge 3$, and $p<p_u(q,\Delta )$, with probability $1-o(1)$ over the choice of a random $\Delta$-regular graph on $n$ vertices, the Glauber dynamics for the random-cluster model has $\Theta (n\log n)$ mixing time. As a corollary, we deduce fast mixing of the Swendsen--Wang dynamics for the Potts model on random $\Delta$-regular graphs for every $q\ge 2$, in the tree uniqueness region. Our proof relies on a sharp bound on the "shattering time", i.e., the number of steps required to break up any configuration into $O(\log n)$ sized clusters. This is established by analyzing a delicate and novel iterative scheme to simultaneously reveal the underlying random graph with clusters of the Glauber dynamics configuration on it, at a given time.

35 pages, 6 figures

References in corpus (9)

• The Random-Cluster Model
• Phase Transitions in the Coloring of Random Graphs
• Ising models on locally tree-like graphs
• Perfect Sampling Using Bounding Chains
• Exact thresholds for Ising-Gibbs samplers on general graphs
• Factor models on locally tree-like graphs
• Glauber Dynamics for the mean-field Potts Model
• Comparison of Swendsen-Wang and Heat-Bath Dynamics
• Rapid mixing of Swendsen-Wang dynamics in two dimensions

Cited by in corpus (4)

• Metastability of the Potts ferromagnet on random regular graphs
• The Critical Mean-field Chayes-Machta Dynamics
• Sampling from the random cluster model on random regular graphs at all temperatures via Glauber dynamics
• Algorithms for the ferromagnetic Potts model on expanders