  We study the mixing time of the Swendsen-Wang dynamics for the ferromagnetic
Ising and Potts models on the integer lattice ${\mathbb Z}^d$. This dynamics is
a widely used Markov chain that has largely resisted sharp analysis because it
is non-local, i.e., it changes the entire configuration in one step. We prove
that, whenever Strong Spatial Mixing (SSM) holds, the mixing time on any
$n$-vertex cube in ${\mathbb Z}^d$ is $O(\log n)$, and we prove this is tight
by establishing a matching lower bound on the mixing time. The previous best
known bound was $O(n)$. SSM is a standard condition corresponding to
exponential decay of correlations with distance between spins on the lattice
and is known to hold in $d=2$ dimensions throughout the high-temperature
(single phase) region. Our result follows from a Modified Log-Sobolev
Inequality, which expresses the fact that the dynamics contracts relative
entropy at a constant rate at each step. The proof of this fact utilizes a new
factorization of the entropy in the joint probability space over spins and
edges that underlies the Swendsen-Wang dynamics, which extends to general
bipartite graphs of bounded degree. This factorization leads to several
additional results, including mixing time bounds for a number of natural local
and non-local Markov chains on the joint space, as well as for the standard
random-cluster dynamics.
