Rapid mixing of Potts Glauber dynamics throughout uniqueness
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 Δ≥ 3, the Potts Glauber dynamics mixes in npolylog(n) steps with high probability on a uniformly random Δ-regular graph for all β<βu(q,𝕋Δ) where βu(q,𝕋Δ) is the uniqueness threshold on the Δ-regular tree; (2) For every d≥ 2, the Potts Glauber dynamics has inverse spectral gap n1+o(1) on cubes or tori in ℤd for all β<βc(q,ℤd) where βc(q,ℤd) is the critical point on ℤ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.
Related
- Glauber Dynamics for Sampling Colorings: Rapid Mixing above (1+1/e)Δ via Hidden Hard-Core Models
- Mixing profile for Glauber dynamics of the discrete Gaussian Free Field starting from super-harmonic functions
- Optimal Mixing of Glauber Dynamics for the Sherrington-Kirkpatrick Model at β< 1/2
- Rank-1-perturbed trickledown theorems: Mixing time of Glauber dynamics for the Sherrington-Kirkpatrick model up to β≤ 1/2+ε
- Near linear mixing of random-cluster Glauber dynamics on random regular graphs
BibTeX
@misc{blanca2026rapid,
title = {{Rapid mixing of Potts Glauber dynamics throughout uniqueness}},
author = {Antonio Blanca and Reza Gheissari and Heehyun Park and Xusheng Zhang},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.42059},
eprint = {2610.42059},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.42059},
}
RIS
TY - UNPB
TI - Rapid mixing of Potts Glauber dynamics throughout uniqueness
AU - Antonio Blanca
AU - Reza Gheissari
AU - Heehyun Park
AU - Xusheng Zhang
PY - 2026
DA - 2026/10/30
PB - arXiv
DO - 10.48550/arxiv.2610.42059
UR - https://arxiv.org/abs/2610.42059
AB - 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 Δ≥ 3, the Potts Glauber dynamics mixes in npolylog(n) steps with high probability on a uniformly random Δ-regular graph for all β<β_u(q,𝕋_Δ) where β_u(q,𝕋_Δ) is the uniqueness threshold on the Δ-regular tree; (2) For every d≥ 2, the Potts Glauber dynamics has inverse spectral gap n^1+o(1) on cubes or tori in ℤ^d for all β<β_c(q,ℤ^d) where β_c(q,ℤ^d) is the critical point on ℤ^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.
ER -