  The Swendsen-Wang dynamics is a popular algorithm for sampling from the Gibbs
distribution for the ferromagnetic Ising model on a graph $G=(V,E)$. The
dynamics is a "global" Markov chain which is conjectured to converge to
equilibrium in $O(|V|^{1/4})$ steps for any graph $G$ at any (inverse)
temperature $\beta$. It was recently proved by Guo and Jerrum (2017) that the
Swendsen-Wang dynamics has polynomial mixing time on any graph at all
temperatures, yet there are few results providing $o(|V|)$ upper bounds on its
convergence time.
  We prove fast convergence of the Swendsen-Wang dynamics on general graphs in
the tree uniqueness region of the ferromagnetic Ising model. In particular,
when $\beta < \beta_c(d)$ where $\beta_c(d)$ denotes the
uniqueness/non-uniqueness threshold on infinite $d$-regular trees, we prove
that the relaxation time (i.e., the inverse spectral gap) of the Swendsen-Wang
dynamics is $\Theta(1)$ on any graph of maximum degree $d \geq 3$. Our proof
utilizes a version of the Swendsen-Wang dynamics which only updates isolated
vertices. We establish that this variant of the Swendsen-Wang dynamics has
mixing time $O(\log{|V|})$ and relaxation time $\Theta(1)$ on any graph of
maximum degree $d$ for all $\beta < \beta_c(d)$. We believe that this Markov
chain may be of independent interest, as it is a monotone Swendsen-Wang type
chain. As part of our proofs, we provide modest extensions of the technology of
Mossel and Sly (2013) for analyzing mixing times and of the censoring result of
Peres and Winkler (2013). Both of these results are for the Glauber dynamics,
and we extend them here to general monotone Markov chains. This class of
dynamics includes for example the heat-bath block dynamics, for which we obtain
new tight mixing time bounds.
