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.