Sampling from Potts on random graphs of unbounded degree via random-cluster dynamics

Antonio Blanca, Reza Gheissari

Published 2021-07-21Version 1

We consider the problem of sampling from the ferromagnetic Potts and random-cluster models on a general family of random graphs via the Glauber dynamics for the random-cluster model. The random-cluster model is parametrized by an edge probability $p \in (0,1)$ and a cluster weight $q > 0$. We establish that for every $q\ge 1$, the random-cluster Glauber dynamics mixes in optimal $\Theta(n\log n)$ steps on $n$-vertex random graphs having a prescribed degree sequence with bounded average branching $\gamma$, throughout the uniqueness regime $p<p_u(q,\gamma)$. Notably, this uniqueness threshold does not decay with the maximum degree and only depends on the average degree. In particular, $p_u(q,\gamma)$ is expected to be sharp, in that for general $q$ and $\gamma$, the random-cluster Glauber dynamics should slow down dramatically at $p_u(q,\gamma)$. The family of random graph models we consider include the Erd\H{o}s--R\'enyi random graph $G(n,\gamma/n)$, and so we provide the first polynomial-time sampling algorithm for the ferromagnetic Potts model on the Erd\H{o}s--R\'enyi random graphs that works for all $q$ in the full uniqueness regime. We accompany our results with mixing time lower bounds (exponential in the maximum degree) for the Potts Glauber dynamics, in the same settings where our $\Theta(n \log n)$ bounds for the random-cluster Glauber dynamics apply. This reveals a significant computational advantage of random-cluster based algorithms for sampling from the Potts Gibbs distribution at high temperatures in the presence of high-degree vertices.