Power Law of Order 1/4 for Critical Mean Field Swendsen-Wang Dynamics

The Swendsen-Wang dynamics is a Markov chain widely used by physicists to sample from the Boltzmann-Gibbs distribution of the Ising model. Cooper, Dyer, Frieze and Rue proved that on the complete graph $K_n$ the mixing time of the chain is at most $O(\sqrt{n})$ for all non-critical temperatures. In this paper the authors show that the mixing time is $\Theta(1)$ in high temperatures, $\Theta(\log n)$ in low temperatures and $\Theta(n^{1/4})$ at criticality. They also provide an upper bound of $O(\log n)$ for Swendsen-Wang dynamics for the $q$-state ferromagnetic Potts model on any tree of $n$ vertices.