The ACO Seminar (2022–2023)

We consider the problem of sampling from the ferromagnetic Potts model on a general family of random graphs that includes random regular graphs and the classical Erdos-Renyi random graph model. Specifically, we present new mixing time bounds for the Glauber dynamics of the random-cluster model and use the well-known connection between the Potts and random-cluster models to efficiently generate samples from the Potts distribution. Our results are tight in the sense that we can prove a matching lower bound for the mixing time and that they apply to an optimal range of model parameters.

Our results also reveal a novel and significant computational advantage of random-cluster-based algorithms for sampling from the Potts distribution at high temperatures. Namely, in the presence of high-degree vertices, random-cluster dynamics mix quickly in near-linear time, but the standard Potts Markov chain may require exponential (in the max degree) time to mix.