Swendsen-Wang Algorithm on the Mean-Field Potts Model

Abstract

We study the $q$-state ferromagnetic Potts model on the $n$-vertex complete graph known as the mean-field (Curie-Weiss) model. We analyze the Swendsen-Wang algorithm which is a Markov chain that utilizes the random cluster representation for the ferromagnetic Potts model to recolor large sets of vertices in one step and potentially overcomes obstacles that inhibit single-site Glauber dynamics. Long et al. studied the case $q=2$, the Swendsen-Wang algorithm for the mean-field ferromagnetic Ising model, and showed that the mixing time satisfies: (i) $Θ(1)$ for $β<β_c$, (ii) $Θ(n^{1/4})$ for $β=β_c$, (iii) $Θ(\log n)$ for $β>β_c$, where $β_c$ is the critical temperature for the ordered/disordered phase transition. In contrast, for $q\geq 3$ there are two critical temperatures $0<β_u<β_{rc}$ that are relevant. We prove that the mixing time of the Swendsen-Wang algorithm for the ferromagnetic Potts model on the $n$-vertex complete graph satisfies: (i) $Θ(1)$ for $β<β_u$, (ii) $Θ(n^{1/3})$ for $β=β_u$, (iii) $\exp(n^{Ω(1)})$ for $β_u<β<β_{rc}$, and (iv) $Θ(\log{n})$ for $β\geqβ_{rc}$. These results complement refined results of Cuff et al. on the mixing time of the Glauber dynamics for the ferromagnetic Potts model.

To appear in Random Structures & Algorithms