| 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 Kn the mixing time of the chain is O( n ) for all non-critical temperatures. We improve their result and provide sharp bounds for the mixing time in all temperatures. We show the mixing time is of order log n at super-critical temperatures, of constant order at sub-critical temperatures, and of order n 1/4 at the critical temperature. We also prove the mixing time is of order log n when the underlying graph is a tree, which improves Cooper and Frieze's early results. The main tool for the proof is understanding the Markov Chain dynamics via properties of critical percolation on the underlying graph. |
