CS Paper Radar

Rapid mixing of Potts Glauber dynamics throughout uniqueness

Antonio Blanca, Reza Gheissari, Heehyun Park, Xusheng Zhang

cs.DM math.PRmath-ph ·submitted 2026-10-30 17:20 UTC · v1
hot direction

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.

Closest papers

Nearest neighbours by meaning across the whole index.

Near linear mixing of random-cluster Glauber dynamics on random regular graphs

cs.DS math.PRmath-ph ·2026-11-04 ·Zhangsong Li
similarity 0.78
Abstract · 37 pages

We study the random-cluster model on locally treelike graphs at low temperatures. This is a model of dependent percolation parametrized by an edge probability $p \in (0,1)$ and a clustering weight $q \in [1,\infty)$, generalizing independent Bernoulli percolation ($q=1$) and closely related to the classical ferromagnetic Ising and Potts spin systems at integer $q$. For $q>2$, at parameter $p$ below the tree uniqueness threshold $p_{\mathsf u}(q,d)$, it is expected that sampling is easy and local Markov chains mix rapidly on all graphs with degree bounded by $d$. On typical graphs, the same is predicted at $p>p_{\mathsf s}(q,d)$, where $p_{\mathsf s}(q,d)$ is a second uniqueness transition point on the $d$-regular wired tree. Our result confirms this prediction for random regular graphs, showing that the random-cluster Glauber dynamics mix in time $O(n^{1+o(1)})$ on a random $d$-regular graph for all fixed $q>2$ and $p>p_{\mathsf s}$. For comparison, the best prior sampling results for these models that held for all $p>p_{\mathsf s}$ required $q\gtrsim \log d$ \cite{BGPZ26}. The key difficulty is that simply utilizing the contraction of cavity messages on $d$-regular trees does not suffice to cover the entire regime $q>2$. To address this issue, motivated by \cite{LS26}, we develop a careful bootstrap argument to show the shrinkage of disagreement under grand coupling. The core ideas of the proof were generated using GPT-6 and the Pharos system; the proof was then refined and simplified by the author.

0.10

Rapid Mixing for Sampling Colorings of Random Graphs up to Tree Uniqueness Threshold

cs.DM math.PRcs.DS ·2026-10-18 ·Zhidan Li, Kuan Yang
theory similarity 0.76
Abstract · 52 pages

We study the mixing time of the single-site Glauber dynamics for sampling proper $q$-colorings on sparse Erdős-Rényi random graphs $\mathcal{G}(n, d/n)$. We prove that, whenever $q \ge (1 + o_d(1))d$, Glauber dynamics mixes in polynomial time with high probability over $\mathcal{G}(n, d/n)$ for all sufficiently large integers $n$. This improves the previous bound $q = (α^* + o_d(1))d$ where $α^* = 1.7632...$ is the unique solution of $x = \exp(1/x)$ on $[1, \infty)$ by Efthymiou, Hayes, Štefankovič, and Vigoda (SODA, 2018) and asymptotically matches the uniqueness threshold on infinite regular trees. Our proof has three main ingredients. First we establish logarithmic bounds on the spectral and coupling independence constants of the Gibbs distribution by extending the tree analysis of Chen, Liu, Mani, and Moitra (J. ACM, 2026). Second, we extend the entropy-factorization framework for two-spin systems on random graphs, developed by Bezáková, Galanis, Goldberg, and Štefankovič (TALG, 2024), to proper colorings by introducing a buffer around high-degree vertices. Finally, we compare the resulting heat-bath block dynamics with the single-site Glauber dynamics.

0.49

Low-Temperature Sampling via Equilibrium Disagreements

cs.DM cs.DSmath.PR ·2026-11-05 ·Andreas Galanis, Daniel Stefankovic
similarity 0.73
Abstract · Abstract shortened to fit arXiv requirements

We develop a new framework for sampling at low temperatures using Glauber dynamics. In this regime, the coexistence of competing modes (commonly referred to as phases) creates bottlenecks that can make worst-case mixing exponentially slow. The main new ingredient in our framework is to relate convergence within a phase to the geometry of disagreements between two independent configurations drawn from that phase. As applications of our approach, we consider three canonical models on random regular graphs that have been central to low-temperature sampling, and establish fast convergence from natural initialisations of Glauber dynamics for every fixed degree. We show: --- For the hard-core model on random bipartite $d$-regular graphs, Glauber dynamics initialised from either one-sided independent set mixes within the corresponding phase in $n^{3/2+o(1)}$ steps throughout the non-uniqueness regime $λ>λ_c(d)$. --- For the random-cluster model on random $d$-regular graphs, for every real $q>2$, Glauber dynamics initialised from the all-in edge set mixes within the ordered phase in $n^{3/2+o(1)}$ steps for all $β\geq β_c$. Similarly, Glauber dynamics initialised from the all-out edge set mixes within the disordered phase in $n^{3/2+o(1)}$ steps for $β\leq β_c$. --- For the ferromagnetic Ising model on random $d$-regular graphs, Glauber dynamics initialised from all-plus or all-minus mixes within the corresponding phase in $n^{3/2+o(1)}$ steps throughout the low-temperature regime $β>β_c(d)$. We also give an $n^{2+o(1)}$-time algorithm that combines phase samples into samples from the full distribution, avoiding in particular time-costly approximations of the corresponding partition functions to the target sampling accuracy.

0.17

Glauber Dynamics for Sampling Colorings: Rapid Mixing above $(1+1/\mathrm{e})Δ$ via Hidden Hard-Core Models

cs.DS cs.DMmath.COmath.PR ·2026-11-03 ·Xiongxin Yang
similarity 0.73
Abstract · 33 pages

We show that for every $γ>0$ and every sufficiently large $Δ$, the Glauber dynamics for proper $q$-colorings of any $n$-vertex graph of maximum degree $Δ$ has spectral gap $Ω_γ(1/n)$, and hence mixing time $O_γ(n^2\log q)$, whenever $q\ge(1+1/\mathrm{e}+γ)Δ$. Our proof establishes a Bochner-type inequality by exploiting the spectral gaps of hard-core models hidden in the color classes. The constant $1+1/\mathrm{e}\approx1.368$ comes from the uniqueness threshold $\approx\mathrm{e}/Δ$ of the hard-core model on the infinite $Δ$-regular tree.

0.19

Improved rapid phase ordering for Ising dynamics on random regular graphs

cs.DS math.PRmath-ph ·2026-10-20 ·Zhangsong Li, Allan Sly
similarity 0.71
Abstract · 59 pages, 3 figures

We study Glauber dynamics for the Ising model on random $d$-regular graphs with $n$ vertices at low temperature, in the regime $β\geq C/d$ where $C,d$ are sufficiently large constants. In this regime, the full mixing time is exponential in $n$, because of the bottleneck between the two dominant phases: configurations with a majority of plus spins and configurations with a majority of minus spins. We show that, for sufficiently large $d$, if the dynamics is initialized with an excess of at least $ε_{C,d} n$ plus spins over minus spins, then it quasi-equilibrates in time $O(\log n)$ to the Gibbs measure conditioned on positive magnetization. In addition, the required bias $ε_{C,d}$ can be chosen so that $ε_{C,d}\to 0$ as $d,C\to\infty$. Previous bound of \cite{GSS25+} in the Ising and large-$d$ setting required $β\gtrsim (\log d)/d$. A key difficulty is that, even from the all-plus initialization, one must control the propagation of negative information in spacetime in a low-temperature model with strong local correlations. We address this by developing a new bootstrap approach to proving subcriticality of disagreement clusters under the grand coupling.

0.32

Sampling Colorings on $G(n, d/n)$ via Glauber Dynamics

cs.DS math.COmath.PR ·2026-11-09 ·Leon Schiller
similarity 0.69
Abstract

We study the mixing time of Glauber dynamics for sampling uniformly from the proper $q$-colorings of sparse Erdős-Rényi random graphs $G(n,d/n)$. Our main result establishes that with probability $1-o(1)$ over the draw of $G$, Glauber dynamics is rapidly mixing for every $q\geq d+d^{1/2+\varepsilon}$, given any fixed $0<\varepsilon\leq1/2$ and any sufficiently large fixed $d$. In particular, the surplus of colors above $d$ is sublinear and close to $\sqrt{d}$. The achieved color range therefore approaches the tree uniqueness threshold and improves over the previously best achievable number of colors $q > 1.763 d$ due to Efthymiou, Hayes, Stefankovic, and Vigoda [SODA 2018]. Moreover, our mixing-time bound is $O(n^{2+o_d(1)})$, and hence almost quadratic as $d\rightarrow\infty$. Our proof is based on establishing a spectral gap for block dynamics resulting from a suitable decomposition of $G(n,d/n)$ into blocks and singleton vertices, ensuring that every high-degree vertex is encapsulated within a block. Our main technical contribution is a novel way of establishing rapid mixing of block dynamics via an integrated Bochner-Bakry-Émery approach, which we expect to have applications beyond sampling colorings. We further devise a new block decomposition of $G(n,d/n)$ that strengthens and simplifies similar constructions used in previous work. Finally, to compare block and Glauber dynamics, we establish a novel recursive separator decomposition of tree-like blocks, together with a coupling argument that avoids the need for nearly uniform color marginals at vertices adjacent to hubs. This comparison argument might be of independent interest.

0.11

A Spectral Local-to-Global Principle for Spin Systems on Graphs with Girth At Least Five

cs.DS cs.DMmath.PR ·2026-08-26 ·Xiaoyu Chen, Kuikui Liu
highly cited similarity 0.69
Abstract

It is proved that, for every $δ\in (0,1)$, the Glauber dynamics for the uniform distribution on proper $q$-colorings is rapidly mixing when $q \geq (1+δ)Δ$ and the underlying graph has girth at least $5$ and maximum degree $Δ= Ω_δ(1)$. This result also extends to general multi-spin systems satisfying a $\textit{local spectral contraction}$ condition, including the anti-ferromagnetic Potts model with $q\geq (1+δ)(1-β)Δ$. These results are achieved by a new spectral local-to-global principle on graphs with girth at least five for general multi-spin systems, and a novel Fourier analysis for Glauber dynamics on a star. The main ideas behind all the proofs were developed through several rounds of interaction with GPT-5.6 Sol Ultra.

0.49

Rapid mixing within a phase for Ising models

cs.DS math.PRmath-ph ·2026-10-16 ·Vasyl Paliy, Youngtak Sohn
theory similarity 0.68
Abstract · 42 pages

We study Glauber dynamics for Ising measures conditioned to have a sufficiently large majority of $+1$ spins. Under a sparse spectral width condition on the interaction matrix, we derive a Poincaré inequality for the conditioned measures from a magnetization drift condition, and a modified logarithmic Sobolev inequality from a stronger, entropy weighted condition. As applications, we obtain approximate posterior sampling in total variation distance for $\mathbb{Z}_2$ synchronization at high enough signal-to-noise ratio using $O(n\log n)$ Glauber updates from a spectral initialization. For ferromagnetic Ising models on random $d$-regular graphs, we prove rapid phase ordering down to inverse temperatures of order $1/d$, extending the temperature range of Gheissari, Sly, and Sohn (2025). Finally, we extend these inequalities to unconditioned Ising measures under an inward drift condition outside the conditioned region. This yields $O(n\log n)$ mixing of Glauber dynamics for the Sherrington-Kirkpatrick model at every fixed inverse temperature when the external field is sufficiently large.

0.20