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

We consider the Ising, and more generally, q-state Potts Glauber dynamics on random d-regular graphs on n vertices at low temperatures β 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≥ 7, from biased initializations with ε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 εd can be taken to zero as d → ∞. Even for the $q=2$ Ising case, where the states are naturally identified with ± 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.