A mathematical preprint reports conditional bounds showing rapid mixing for Glauber dynamics applied to uniform proper q-colorings on finite simple graphs whose shortest cycle has length at least five. Proper colorings require neighboring vertices to receive different colors. The result says the dynamics is irreducible and has a spectral-gap lower bound of Omega_delta(1/n), where n is the number of vertices. It also gives the mixing-time upper bound O_delta(n log q + n log(1/epsilon)) for epsilon between 0 and 1, provided q is at least (1 + delta) times the maximum degree Delta and Delta is sufficiently large in terms of delta.
In plain terms, the spectral gap is the quantity the paper uses to express how quickly the chain can shed dependence on its starting state, while the mixing time is the stated time needed to get close to the target distribution. The first is bounded from below and the second from above. Neither is a measured runtime: the claims are asymptotic statements about theoretical graph instances.
Why five matters
The paper presents the girth condition as its main comparison point. It claims to improve the required girth for the coloring result from 11 in a cited recent result to 5. Girth means the length of a graph's shortest cycle, so the stated assumption is that no cycle shorter than five appears in the finite graph under study. The comparison concerns theoretical graph instances, not an empirical participant sample.
From stars to whole graphs
The proof's central device is a spectral local-to-global principle. It reduces the global continuous-time spectral gap to weighted dynamics on closed stars, under conditional independence, local spectral-gap assumptions and a neighborhood-reserve condition. A closed star is a vertex together with its neighbors. The paper combines this reduction with Fourier analysis for Glauber dynamics on a star.
The framework is not limited to proper colorings. Its general contraction theorem covers multi-spin systems on n-vertex graphs with girth at least five. When local (alpha, epsilon)-spectral contraction holds, the maximum degree Delta is sufficiently large in terms of alpha and epsilon and is at least 2 alpha, and the dynamics is irreducible, the theorem gives a spectral-gap lower bound Omega_{alpha,epsilon}(1/n). That is an inverse-linear lower bound, not a claim that every instance has an exact gap equal to a fixed constant times 1/n.
The local analysis focuses on a star. A star-level theorem gives a Poincare inequality, a relation between variance and the update operator used in spectral analysis, when r is less than 1/5 and eta is below 1. Under Condition 26 and Delta at least 2 alpha, a further lemma bounds the projected center-update norm by O_alpha(1/Delta). It also bounds the squared degree-one block, whose leading term is (1 - epsilon)/Delta, with lower-order terms involving log(2d) and Delta to the three-halves power. These estimates provide the local contraction input for the broader reduction.
The framework reaches the Potts model
The authors then apply the framework to the anti-ferromagnetic q-state Potts model, a broader multi-spin system. On finite simple graphs with girth at least five, and for beta from 0 through 1, the paper reports irreducibility and a spectral-gap lower bound Omega_delta(1/n) when q is at least (1 + delta)(1 - beta)Delta and Delta is sufficiently large.
The corresponding Potts mixing bounds split into two regimes. At beta = 0, the stated upper bound is O_delta(n log q + n log(1/epsilon)). For 0 < beta <= 1, it becomes O_delta(n log q + n Delta log(1/beta) + n log(1/epsilon)), adding a degree-dependent term. These are asymptotic upper bounds under the theorem's assumptions, rather than measured runtimes.
For the Potts application, the proof uses B equal to theta times I and verifies Condition 4 with alpha = 1/delta and epsilon = delta/(1 + delta). The paper uses that verification to supply the local condition required by the general contraction theorem.
The boundaries remain clear
None of these statements removes the theorem's conditions. The coloring result requires girth at least five, q at least (1 + delta)Delta and sufficiently large Delta. The general theorem requires local spectral contraction and irreducibility, while the Potts statement has its own beta-dependent color condition. The paper therefore does not establish the same rapid-mixing guarantee for arbitrary graphs outside these settings.
The authors specifically state that spanning 4-cycles break both the local-to-global argument and the local analysis. The reported results are asymptotic bounds for theoretical graph and spin-system instances, not empirical runtime measurements or benchmark results.
A mathematical preprint with AI disclosure
The document is an arXiv preprint, version 1, dated 26 Aug 2026. Its abstract says the main ideas behind the proofs were developed through several rounds of interaction with GPT-5.6 Sol Ultra. The paper acknowledges support from NSF CAREER grant CCF-2443045 and the Reed Fund at MIT.
Because the unit of analysis is a finite graph or spin-system instance, the work is a methods contribution about proving mixing bounds for mathematical dynamics and proof conditions.
Paper data and sources
Original title: A Spectral Local-to-Global Principle for Spin Systems on Graphs with Girth At Least Five
Authors: Xiaoyu Chen, Kuikui Liu
Journal/Repository: arXiv
Status: Preprint, not yet peer-reviewed
First online: 2026-08-26
DOI: Not available
Original paper · Full text