Swendsen‐Wang dynamics for general graphs in the tree uniqueness region

The Swendsen‐Wang (SW) dynamics is a popular Markov chain for sampling from the Gibbs distribution for the ferromagnetic Ising model on a graph G  = ( V , E ). The dynamics is conjectured to converge to equilibrium in O (| V | 1/4 ) steps at any (inverse) temperature β , yet there are few results providing o (| V |) upper bounds. We prove fast convergence of the SW dynamics on general graphs in the tree uniqueness region. In particular, when β  <  β c ( d ) where β c ( d ) denotes the uniqueness/nonuniqueness threshold on infinite d ‐regular trees, we prove that the relaxation time (i.e., the inverse spectral gap) of the SW dynamics is Θ(1) on any graph of maximum degree d  ≥ 3. Our proof utilizes a monotone version of the SW dynamics which only updates isolated vertices. We establish that this variant of the SW dynamics has mixing time O ( log | V | ) and relaxation time Θ(1) on any graph of maximum degree d for all β  <  β c ( d ). Our proof technology can be applied to general monotone Markov chains, including for example the heat‐bath block dynamics , for which we obtain new tight mixing time bounds.