Source-linked AI summary
A Spectral Local-to-Global Principle for Spin Systems on Graphs with Girth At Least Five
Xiaoyu Chen, Kuikui Liu
TL;DR
Efficient sampling from proper q-colorings remains difficult when q is close to the maximum degree. This paper proves rapid-mixing results for Glauber dynamics on girth-at-least-five graphs, extends them to spin systems, and develops local spectral and star-based analyses.
Problem
Efficient sampling from the uniform distribution on proper q-colorings when q is close to the maximum degree remains a major open problem.
Method
The paper uses a spectral local-to-global principle, weighted star Glauber dynamics, and Schur-complement reductions for local operator inequalities.
Results
The Glauber dynamics for proper q-colorings on girth-at-least-five graphs is irreducible, has spectral gap Ω_δ(1/n), and improves the prior girth requirement from 11 to 5.
Takeaways & Limitations
The results provide a girth-five rapid-mixing guarantee for proper colorings and extend the framework to anti-ferromagnetic Potts models.
Takeaways & Limitations
Spanning 4-cycles break both the local-to-global argument and the local analysis, and the manuscript does not include the proposed extension to graphs without spanning 4-cycles.
Abstract
from arXiv · showhide
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.
1 Introduction
The paper proves rapid mixing for Glauber dynamics on proper colorings of girth-at-least-five graphs near the degree threshold, and extends the framework to multi-spin systems. Its approach reduces global spectral-gap estimates to local star analyses, while improving the girth requirement and preserving polynomial dependence on 1/δ.
- Theorem 1: q ≥ (1+δ)∆ yields rapid mixing for proper q-colorings on girth-at-least-five graphs when ∆ is sufficiently large in terms of δ.The Glauber dynamics is irreducible, has spectral gap Ωδ(1/n), and satisfies the theorem’s stated mixing bound.
- Theorem 1: The result improves the prior girth requirement from 11 to 5 for the near-threshold coloring regime.The comparison is explicitly made with the recent result of [JMV26].
- General framework: For the antiferromagnetic Potts model, the paper proves irreducibility, spectral gap Ωδ(1/n), and the stated mixing bound under its q, β, ∆, and girth conditions.The uniform proper-coloring theorem is identified as a special case of the Potts result.
- General framework: The framework applies to general multi-spin systems with local (α, ε)-spectral contraction and gives spectral gap Ωα,ε(1/n) on girth-at-least-five graphs.The theorem also assumes sufficiently large ∆ and irreducibility of the Glauber dynamics.
- Proof strategy: A Bochner-type identity reduces the global spectral-gap problem to Glauber dynamics on stars, whose gaps are analyzed using a novel Fourier analysis.The local-to-global theorem and star analysis form the paper’s main proof mechanism.
- Discussion and scope: The approach avoids self-avoiding-walk trees and has polynomial rather than exponential dependence on 1/δ, although spanning 4-cycles obstruct the current argument.The authors report that spanning 4-cycles break both the local-to-global argument and the local analysis.
2 Preliminaries
The preliminaries define spin systems, finite-dimensional inner-product and operator notation, spectral-gap and mixing concepts, and the Laplacian formulation of Glauber dynamics.
- The notation introduces neighborhoods, graph distance, girth, conditional variance, indicators, and the mean-zero subspace 1⊥.
- A spin system is a probability distribution on configurations in [q]^V, with pinnings specifying feasible assignments outside a vertex subset.
- An inner-product space supplies norms, orthogonality, projections, operator restrictions, kernels, ranges, adjoints, and positive-semidefinite ordering.
- The Schur complement reduces positivity of an operator on an orthogonal direct sum to positivity of an effective operator on one subspace.
- For reversible positive-semidefinite Markov chains, the spectral gap is characterized by the Poincaré inequality and Rayleigh–Ritz variational principle.
- 2.5 Glauber dynamics and its Laplacians: The discrete-time Glauber Laplacian is L/n, its gap is the smallest eigenvalue of L on 1⊥ divided by n, and weighted continuous-time dynamics use sums of single-site Laplacians.
3 A local-to-global principle for girth-5 spin systems
On girth-at-least-five graphs, conditional independence and local weighted spectral-gap bounds combine through a Bochner-type argument to yield a global spectral-gap guarantee.
- The star-local dynamics update the center at rate one and each leaf at rate (1 + ηv)/2.
- Theorem 20 gives global continuous-time spectral gap at least ε/2 when local parameters satisfy the pinning conditions and ∑u∈N(v) ηu ≤ 1 − ε.
- The local-to-global proof expands the squared Laplacian and discards distant pairs because update projections commute at graph distance at least two.
- Girth at least five ensures neighborhoods are independent around each vertex and distance-two vertex pairs have unique common neighbors, enabling local double counting.
- Conditioning outside a closed neighborhood reduces global single-site Laplacians to the corresponding pinned local dynamics, whose weighted sums retain the same proof structure.
4 A Fourier analysis for continuous-time Glauber dynamics on a star
The star analysis decomposes functions into orthogonal Hoeffding components and uses block-operator inequalities to establish a Poincaré bound for weighted continuous-time Glauber dynamics.
- Conditional independence of leaves given the center makes leaf heat-bath projections and single-site Laplacians commute.
- The orthogonal Hoeffding expansion partitions 1⊥ into degree-zero, degree-one, and higher-order components K0, K1, and K2.
- The combined subspace K+ := K1 ⊕ K2 supports the block-operator formulation used for the star inequality.
- The resulting Poincaré inequality provides the star-local estimate required by the girth-five local-to-global argument.
- The proof applies Schur complements to reduce positivity of the block operator and controls the remaining blocks using the feedback parameter η.
5 Rapid mixing via local spectral contraction
The section proves a local-to-global spectral-gap theorem for multi-spin systems on girth-at-least-five graphs by analyzing conditioned star neighborhoods. Uniform local weighted gap estimates and conditional independence yield global rapid mixing.
- Local star analysis: Condition 26 supplies the marginal and contraction hypotheses needed for the local star estimates.The section verifies the hypotheses of Theorem 20 through Lemma 27 and its supporting propositions.
- Local star analysis: Girth at least 5 makes each conditioned neighborhood N[v] a star whose leaves are independent given the center.This structure enables the local analysis on star gadgets.
- Local-to-global step: The resulting weighted spectral-gap estimate holds uniformly over all feasible pinnings τ.This is the local input required by the spectral local-to-global theorem.
- Local-to-global step: Conditional independence and the uniform local estimate give continuous-time spectral gap at least ε/4, and discrete-time gap at least ε/(4n).The discrete-time Laplacian is L/n, so its gap inherits the corresponding 1/n scaling.
- Local star analysis: Proposition 32 controls the relevant leaf-dynamics quantities uniformly when ∆≥2α, using independence and concentration.Its proof invokes McDiarmid’s inequality after exploiting independence under the conditioned star laws.
6 Application to the anti-ferromagnetic Potts model
The section applies the general theorem to the anti-ferromagnetic q-state Potts model by verifying local spectral contraction uniformly over vertices and feasible pinnings. This yields a discrete-time spectral-gap bound and completes the theorem.
- Model specialization: For the anti-ferromagnetic Potts model, the interaction matrix is parameterized by ϑ := 1 − β and the proof verifies Condition 4.The argument specializes the general multi-spin framework to the Potts interaction.
- Model specialization: Girth at least 5 makes each conditioned neighborhood a star, allowing the neighbor-color counts and tree recursion to determine the local marginals.Pinned neighbors outside N[v] enter through the quantities k_i,a.
- Contraction verification: The contraction estimates are uniform over every vertex and feasible pinning, establishing local spectral contraction for the Potts measure.The resulting parameters are (δ^-1, δ/(1 + δ)).
- Global conclusion: After irreducibility and the theorem’s hypotheses are verified, the discrete-time Glauber dynamics obtains the claimed spectral-gap bound.The proof treats β>0 through full support and β=0 through the proper-coloring irreducibility condition.
- Global conclusion: Configuration-mass estimates are combined with the spectral-gap estimate in the standard worst-start mixing bound to conclude rapid mixing.Separate mass bounds are considered for β=0 and 0<β≤1.