  The random-cluster model is a unifying framework for studying random graphs,
spin systems and electrical networks that plays a fundamental role in designing
efficient Markov Chain Monte Carlo (MCMC) sampling algorithms for the classical
ferromagnetic Ising and Potts models. In this paper, we study a natural
non-local Markov chain known as the Chayes-Machta dynamics for the mean-field
case of the random-cluster model, where the underlying graph is the complete
graph on $n$ vertices. The random-cluster model is parametrized by an edge
probability $p$ and a cluster weight $q$. Our focus is on the critical regime:
$p = p_c(q)$ and $q \in (1,2)$, where $p_c(q)$ is the threshold corresponding
to the order-disorder phase transition of the model. We show that the mixing
time of the Chayes-Machta dynamics is $O(\log n \cdot \log \log n)$ in this
parameter regime, which reveals that the dynamics does not undergo an
exponential slowdown at criticality, a surprising fact that had been predicted
(but not proved) by statistical physicists. This also provides a nearly optimal
bound (up to the $\log\log n$ factor) for the mixing time of the mean-field
Chayes-Machta dynamics in the only regime of parameters where no non-trivial
bound was previously known. Our proof consists of a multi-phased coupling
argument that combines several key ingredients, including a new local limit
theorem, a precise bound on the maximum of symmetric random walks with varying
step sizes, and tailored estimates for critical random graphs. In addition, we
derive an improved comparison inequality between the mixing time of the
Chayes-Machta dynamics and that of the local Glauber dynamics on general
graphs; this results in better mixing time bounds for the local dynamics in the
mean-field setting.
