Rapid phase ordering for Ising and Potts dynamics on random regular graphs

Abstract

We consider the Ising, and more generally, $q$-state Potts Glauber dynamics on random $d$-regular graphs on $n$ vertices at low temperatures ${\hat{I}}^2\gtrsim \frac{\log d}{d}$. The mixing time is exponential in $n$ due to a bottleneck between $q$ dominant phases consisting of configurations in which the majority of vertices are in the same state. We prove that for any $d\ge 7$, from biased initializations with $\hat{I}{\mu }_{d}n$ more vertices in state-$1$ than in other states, the Glauber dynamics quasi-equilibrates to the stationary distribution conditioned on having plurality in state-$1$ in optimal $O(\log n)$ time. Moreover, the requisite initial bias $\hat{I}{\mu }_d$ can be taken to zero as $d\to \infty$. Even for the $q=2$ Ising case, where the states are naturally identified with $\pm 1$, proving such a result requires a new approach in order to control negative information spread in spacetime despite the model being in low temperature and exhibiting strong local correlations. For this purpose, we introduce a coupled non-Markovian rigid dynamics for which a delicate temporal recursion on probability mass functions of minus spacetime cluster sizes establishes their subcriticality.

41 pages, 2 figures