  Sampling from the $q$-state ferromagnetic Potts model is a fundamental
question in statistical physics, probability theory, and theoretical computer
science. On general graphs, this problem is computationally hard, and this
hardness holds at arbitrarily low temperatures. At the same time, in recent
years, there has been significant progress showing the existence of
low-temperature sampling algorithms in various specific families of graphs. Our
aim in this paper is to understand the minimal structural properties of general
graphs that enable polynomial-time sampling from the $q$-state ferromagnetic
Potts model at low temperatures. We study this problem from the perspective of
the widely-used Swendsen--Wang dynamics and the closely related random-cluster
dynamics.
  Our results demonstrate that the key graph property behind fast or slow
convergence time for these dynamics is whether the independent edge-percolation
on the graph admits a strongly supercritical phase. By this, we mean that at
large $p<1$, it has a unique giant component of linear size, and the complement
of that giant component is comprised of only small components. Specifically, we
prove that such a condition implies fast mixing of the Swendsen--Wang and
random-cluster dynamics on two general families of bounded-degree graphs: (a)
graphs of at most stretched-exponential volume growth and (b) locally treelike
graphs. In the other direction, we show that, even among graphs in those
families, these Markov chains can converge exponentially slowly at arbitrarily
low temperatures if the edge-percolation condition does not hold. In the
process, we develop new tools for the analysis of non-local Markov chains,
including a framework to bound the speed of disagreement propagation in the
presence of long-range correlations, and an understanding of spatial mixing
properties on trees with random boundary conditions.
