Potts model sampling mixes quickly on key graph types below critical temperature
Rapid mixing of Potts Glauber dynamics throughout uniqueness
Discrete Mathematics
Summary
Sampling from the Potts model, a mathematical way to study magnetism and similar systems, can be very slow or very fast depending on temperature. The authors show that on two important types of graphs, Glauber dynamics—a natural random process for sampling states—mixes rapidly at all high temperatures where the model behaves nicely. They introduce a new principle that either the system's constraints allow quick mixing or the process quickly moves away from difficult configurations. This improves understanding and guarantees efficient sampling in complex models without relying on prior assumptions.
What this means in practice
- •For statistical physics simulation teams: Ensure fast and reliable sampling of states in ferromagnetic Potts models on random regular graphs under high-temperature conditions for simulation studies.
- •For computational physics software developers: Implement efficient single-site and cluster-based sampling algorithms for the Potts model on lattice structures like cubes and tori ensuring rapid convergence below critical temperatures.
Authors
Antonio Blanca, Reza Gheissari, Heehyun Park, Xusheng Zhang
Abstract
Sampling from the ferromagnetic $q$-state Potts model is a fundamental problem in statistical physics and approximate counting. Although computationally hard in the worst case, sampling is expected to be efficient throughout the high-temperature uniqueness regime of the model using the natural single-site Glauber dynamics. We establish fast mixing bounds for every $q$, in the full high-temperature regimes in the two central graph families on $n$ vertices. (1) For every $Δ\ge 3$, the Potts Glauber dynamics mixes in $n\operatorname{polylog}(n)$ steps with high probability on a uniformly random $Δ$-regular graph for all $β<β_u(q,\mathbb T_Δ)$ where $β_u(q,\mathbb T_Δ)$ is the uniqueness threshold on the $Δ$-regular tree; (2) For every $d\ge 2$, the Potts Glauber dynamics has inverse spectral gap $n^{1+o(1)}$ on cubes or tori in $\mathbb Z^d$ for all $β<β_c(q,\mathbb Z^d)$ where $β_c(q,\mathbb Z^d)$ is the critical point on $\mathbb Z^d$. Both temperature thresholds are sharp as the Glauber dynamics slows down exponentially above them. These results overcome the challenge of bounding mixing times without access to correlation decay bounds in the presence of pinnings (i.e., without spectral independence or strong spatial mixing). For this purpose, our proof introduces a new dichotomy principle: throughout the high-temperature regime, any initial spin distribution is either such that its pinnings ensure good correlation decay, or Glauber dynamics escapes from that distribution quickly. We expect this kind of dichotomy to have further applications. As a demonstration, we also develop its analog for random-cluster dynamics and use it to prove that Swendsen-Wang dynamics on random $Δ$-regular graphs mixes in $O(\log n)$ time throughout uniqueness. The results in this paper were arrived at with the assistance of ChatGPT 5.6 and 6.