Swendsen-Wang algorithm on the mean-field Potts model - Galanis, A; Stefankovic, D; Vigoda, E (Wiley, 2018)
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≥ 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 $β≥β_{rc}$. These results complement refined results of Cuff et al. on the mixing time of the Glauber dynamics for the ferromagnetic Potts model.