  The Swendsen-Wang algorithm is a sophisticated, widely-used Markov chain for
sampling from the Gibbs distribution for the ferromagnetic Ising and Potts
models. This chain has proved difficult to analyze, due in part to the global
nature of its updates. We present optimal bounds on the convergence rate of the
Swendsen-Wang algorithm for the complete $d$-ary tree. Our bounds extend to the
non-uniqueness region and apply to all boundary conditions.
  We show that the spatial mixing conditions known as Variance Mixing and
Entropy Mixing, introduced in the study of local Markov chains by Martinelli et
al. (2003), imply $\Omega(1)$ spectral gap and $O(\log{n})$ mixing time,
respectively, for the Swendsen-Wang dynamics on the $d$-ary tree. We also show
that these bounds are asymptotically optimal. As a consequence, we establish
$\Theta(\log{n})$ mixing for the Swendsen-Wang dynamics for all boundary
conditions throughout the tree uniqueness region; in fact, our bounds hold
beyond the uniqueness threshold for the Ising model, and for the $q$-state
Potts model when $q$ is small with respect to $d$. Our proofs feature a novel
spectral view of the Variance Mixing condition inspired by several recent rapid
mixing results on high-dimensional expanders and utilize recent work on block
factorization of entropy under spatial mixing conditions.
