  Swendsen-Wang dynamics for the Potts model was proposed in the late 1980's as
an alternative to single-site heat-bath dynamics, in which global updates allow
this MCMC sampler to switch between metastable states and ideally mix faster.
Gore and Jerrum (1999) found that this dynamics may in fact exhibit slow
mixing: they showed that, for the Potts model with $q\geq 3$ colors on the
complete graph on $n$ vertices at the critical point $\beta_c(q)$,
Swendsen-Wang dynamics has $t_{\mathrm{mix}}\geq \exp(c\sqrt n)$. The same
lower bound was extended to the critical window $(\beta_s,\beta_S)$ around
$\beta_c$ by Galanis et al. (2015), as well as to the corresponding mean-field
FK model by Blanca and Sinclair (2015). In both cases, an upper bound of
$t_{\mathrm{mix}} \leq \exp(c' n)$ was known. Here we show that the mixing time
is truly exponential in $n$: namely, $t_{\mathrm{mix}} \geq \exp (cn)$ for
Swendsen-Wang dynamics when $q\geq 3$ and $\beta\in(\beta_s,\beta_S)$, and the
same bound holds for the related MCMC samplers for the mean-field FK model when
$q>2$.
