A Spectral Local-to-Global Principle for Spin Systems on Graphs with Girth At Least Five
Listen
Radio episode about this paper
Transcript
Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.
Tom: We're looking at the paper: "A Spectral Local-to-Global Principle for Spin Systems on Graphs with Girth At Least Five".
Jane: Here's the gist of the paper. It is proved that, for every δ ∈ (0, 1), the Glauber dynamics for the uniform distribution on proper q-colorings is rapidly mixing when q ≥ (1 + δ)∆ and the underlying graph has girth at least 5 and maximum degree ∆ = omegaδ(1) <ref:2608.25491/pg3.
Tom: Local-to-Global Principle The paper introduces a new spectral local-to-global principle for general multi-spin systems on graphs with girth at least five <ref:2608.25491#pg4>.
Jane: This principle is crucial because it allows the reduction of the spectral gap of Glauber dynamics on the whole graph to estimates on stars, which are local gadgets <ref:2608.25491#pg8>.
Tom: The main ideas behind all the proofs were developed through several rounds of interaction with GPT-5.6 Sol Ultra <ref:2608.25491#pg4>.
Title and authors: Tom: So we’re looking at this paper, it’s called "A Spectral Local-to-Global Principle for Spin Systems on Graphs with Girth At Least Five". It sounds really technical and a bit abstract, but it’s about making sure these complex systems mix well.
Jane: I always start by asking what this is actually about for someone who isn't deep in spectral graph theory. Basically, it’s proposing a new way to understand how fast things mix when you have certain types of structures in the graph, specifically graphs with no small cycles.
Lu: The authors are connecting local properties—things happening near one spot—to global properties—how the whole system mixes across the entire graph. They’re using this idea to prove rapid mixing for a lot more than just simple coloring problems.
Meng: I'm wondering if this new principle actually translates into something practical when we try to deploy these models at scale, you know, on massive graphs where things get really dense.
Lalam: Based on the abstract, it seems like they’re extending results that work for simple uniform distributions onto general multi-spin systems using a condition called local spectral contraction.
The paper's summary: Tom: The core of this paper is proving that for every delta smaller than one, if you have a graph with at least five cycles and the maximum degree is bounded by some value proportional to delta, then the Glauber dynamics for uniform distributions on proper q-colorings mixes rapidly as long as q is greater than one plus that delta.
Jane: So what does that mean practically? It means we can sample from these proper colorings much faster than before, especially when the number of available colors isn't huge compared to how connected the graph is.
Lu: The paper builds this by introducing a spectral local-to-global principle that lets them reduce the mixing time estimates for the whole graph down to just analyzing smaller pieces, like stars, which are local gadgets.
Meng: Reducing it to local analysis sounds promising if we can actually trust those local estimates when they apply globally on a large system where updates are spread out.
Lalam: They use this principle and a new Fourier analysis for continuous-time Glauber dynamics on star graphs to set up a Poincaré inequality, which is the key tool for getting those mixing time bounds.
The paper's improvements: Tom: One of the big improvements they highlight is that this method works for general multi-spin systems satisfying a local spectral contraction condition, not just uniform distributions on colorings.
Jane: That’s a big deal because it means this isn't just a trick for one specific type of problem; it applies to many different kinds of physical models, like those anti-ferromagnetic Potts models.
Lu: They show that by using this local spectral contraction condition, you can establish a spectral gap for the whole graph that is at least some constant times one over n, which implies rapid mixing.
Meng: If the spectral gap is guaranteed to be proportional to one over n, that gives us a concrete measure of how fast it mixes globally on a large structure. That’s something I can actually use for setting performance targets.
Lalam: The paper provides specific mixing time bounds, like t mix epsilon equals big O of delta to the power of n over two log q plus n log one over epsilon when beta is zero, and a slightly different bound involving beta when it's positive <ref:2608.25491#pg1>.
Conclusion: Tom: To wrap up, this paper essentially gives us a new spectral local-to-global principle for spin systems on graphs with at least five cycles. It confirms rapid mixing for uniform colorings under certain degree constraints and extends that to general multi-spin systems using the local spectral contraction condition.
Jane: The implication is that we have a more robust framework for analyzing how fast these complex probabilistic models converge to their steady state, especially when dealing with physical models like the anti-ferromagnetic Potts model.
Lu: It’s a powerful tool because it lets us translate difficult global mixing problems into simpler local ones, which is what the spectral local-to-global principle achieves.
Meng: For deployment, this means we have better theoretical guarantees on performance for these complex systems than we had before, specifically when dealing with those interaction parameters like beta.
Lalam: So, the final results show that the discrete-time Glauber dynamics has a spectral gap of at least some constant times one over n.
Massachusetts Institute of Technology
cs.DS, cs.DM, math.PR
Submitted: 2026-08-26
Updated: 2026-11-03
License: http://creativecommons.org/licenses/by/4.0/
Importance score: 69/100
The gist: It is proved that, for every δ ∈ (0, 1), the Glauber dynamics for the uniform distribution on proper q-colorings is rapidly mixing when q ≥ (1 + δ)∆ and the underlying graph has girth at…
Key concepts
- Local-to-Global Principle
- This new principle connects the spectral gap of a complex system across an entire graph to simpler estimates on small, local gadgets like stars. It's a crucial tool because it simplifies the analysis of global dynamics by focusing on how local updates propagate information across the network.
- Spectral Gap
- The spectral gap measures how quickly a Markov chain mixes. A larger spectral gap means the system converges to its stationary distribution much faster. The paper establishes both continuous-time and discrete-time bounds for this gap, which are essential for proving rapid mixing.
- Girth at Least Five
- Girth refers to the length of the shortest cycle in a graph. Requiring girth at least five ensures that local structures are tree-like enough (no short cycles) to allow the local-to-global argument to work effectively, preventing problematic interactions from forming too quickly.
- Anti-ferromagnetic Potts Model
- This is a specific type of multi-spin system where the energy depends on whether neighboring spins are the same or different. When the interaction parameter $\beta=0$, it simplifies to uniform proper $q$-colorings, and the paper provides precise mixing time bounds for this model based on $q$ and other system parameters.
Terminology
Summary
It is proved that, for every δ ∈ (0, 1), the Glauber dynamics for the uniform distribution on proper q-colorings is rapidly mixing when q ≥ (1 + δ)∆ and the underlying graph has girth at least 5 and maximum degree ∆ = omegaδ(1) <ref:2608. p. 0 A Spectral Local-to-Global Principle for Spin
Systems on Graphs with Girth At Least Five
Xiaoyu Chen∗ Kuikui Liu†
Abstract
It is proved that, for every δ ∈ (0, 1), the Glauber dynamics for the uniform
distribution on proper q-colorings is rapidly mixing when q ≥ (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 local spectral contraction
condition, including the anti-ferromagnetic Potts model with q ≥ (1 + δ)(1 − β)∆.Where the paper says it
Local-to-Global Principle
The paper introduces a new spectral local-to-global principle for general multi-spin systems on graphs with girth at least five <ref:2608.25491#pg4>. This principle is crucial because it allows the reduction of the spectral gap of Glauber dynamics on the whole graph to estimates on stars, which are local gadgets <ref:2608. p. 4 The proof of Theorem 5 is deferred to Section 5. To obtain Theorem 5, we introduce
a local-to-global theorem (Theorem 20) via the Bochner-type identity (Proposition 16),
which reduces the spectral gap of Glauber dynamics on the whole graph (global) to
the spectral gap of Glauber dynamics on stars (local). 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. The main ideas behind all the proofs were developed
through several rounds of interaction with GPT-5. 6 Sol Ultra. The main ideas behind all the proofs were developed
through several rounds of interaction with GPT-5. 6 Sol Ultra. The main ideas behind all the proofs were developed
through several rounds of interaction with GPT-5. 6 Sol Ultra.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Spectral Gap and Mixing Time Bounds
The paper establishes a spectral gap for the continuous-time Glauber dynamics on graphs with girth at least 5 <ref:2608.25491#pg11>. Specifically, Theorem 20 shows that if certain conditions on the local dynamics hold, the continuous-time Glauber Laplacian has a spectral gap at least ε/2 <ref:2608. p. 4 We say µG has local (α,ε)-spectral contraction if,
with B := 11⊺ − A, the following conditions hold for every v ∈ V and every feasible
pinning τ ∈ [q]
V\N[v]
:
• it has α-bounded marginals:
Bµ
τ
G,v
∞
≤ α/∆, and
Bµ
τ
G−v,i
∞
≤ α/∆, ∀i ∈ N(v);
• it has ε-contraction:
diag
∑
i∈N(v)
µ
τ
G−v,i
1/2
B diag µ
τ
G,v
1/2
2
2
≤
1 − ε
∆
,
where we treat marginal probabilities µ
τ
G,v
and µ
τ
G−v,i
as vectors in Rq and all norms
above are defined in Euclidean space. Suppose G is an n-vertex simple graph with maximum degree ∆ and girth at least
5. Discrete versions
were developed for finite Markov chains and interacting-particle systems [BCDP06,
CP07, Cap08, CDP09, DP13, Maa11, EM12, Mie13, EMT15, FM16, EHMT17, EF18], with
more recent extensions involving Beckner and curvature-dimension inequalities and
coupling-based curvature bounds [JY17, WZ21, Ped25]. Related squared-generator
expansions have also been applied to spectral-gap estimates for hard-core and antiferromagnetic two-spin models [KKO13, GJM+26, GZ26].Where the paper says it
Where the paper says it
Analysis on Star Graphs
A novel Fourier analysis is developed for continuous-time Glauber dynamics on a star graph <ref:2608.25491#pg14>. This analysis involves an orthogonal Hoeffding expansion and the decomposition of the space into three orthogonal subspaces K0, K1, and K2 <ref:2608. p. 7 For two vectors
f , g ∈ H, we say f ⊥ g if ⟨f , g⟩H = 0. For subspaces K0, K1 ⊆ H, the notation K0 ⊥ K1
means that every vector in K0 is orthogonal to every vector in K1. By the Rayleigh–Ritz variational principle,
1 − λ2(P) = inf
f ̸=0
f⊥1
⟨f ,Lf⟩µ
⟨f , f⟩µ
. Equivalently, 1 − λ2(P) is the largest constant γ for which the Poincaré inequality
γ ⟨f , f⟩µ ≤ ⟨f ,Lf⟩µ
, f ⊥ 1,
holds.Where the paper says it
Where the paper says it
Application to Potts Models
The results extend to general multi-spin systems, including the anti-ferromagnetic Potts model <ref:2608.25491#pg4>. Theorem 3 generalizes the mixing time bounds for this model, yielding tmix(ε) = Oδ(n/2 log q + n log 1/ε) when β = 0 and tmix(ε) = Oδ(n/2 log q + n 2∆ log 1/β + n log 1/ε) when 0. p. 3 Let G = (V, E) be a finite simple graph on n vertices with
maximum degree ∆ and girth at least 5, let β ∈ [0, 1], and let q be an integer. If ∆ is sufficiently
large in terms of δ and
q ≥ (1 + δ)(1 − β)∆,
then the Glauber dynamics for the anti-ferromagnetic q-state Potts model with interaction
parameter β is irreducible, has spectral gap Ωδ(1/n), and satisfies
tmix(ε) = Oδ
n
2
log q + n log 1
ε
, ε ∈ (0, 1), (1)
when β = 0.Where the paper says it
Rapid Mixing via Local Contraction
The rapid mixing is achieved by showing that the local spectral contraction condition implies a spectral gap of Ωδ(1/n) for the global dynamics <ref:2608.25491#pg6>. This relies on Lemma 27, which bounds the relevant operators (Pv) in terms of α and ∆ <ref:2608. p. 8 Thus ⪰ is an order on self-adjoint operators, not an entry-wise inequality. All spectra
below consist of eigenvalues; multiplicities are stated explicitly when relevant.Where the paper says it
Proof Techniques
The proof of Proposition 35 involves combining Proposition 34 and Proposition 36 to show that the contraction condition is satisfied using a carefully chosen parameter ηb <ref:2608.25491#pg19>. The final steps involve applying Theorem 25 to obtain the required Poincaré inequality <ref:2608. p. 9 By the Rayleigh–Ritz variational principle,
1 − λ2(P) = inf
f ̸=0
f⊥1
⟨f ,Lf⟩µ
⟨f , f⟩µ
. Equivalently, 1 − λ2(P) is the largest constant γ for which the Poincaré inequality
γ ⟨f , f⟩µ ≤ ⟨f ,Lf⟩µ
, f ⊥ 1,
holds.Where the paper says it
Girth Constraints
The necessity of girth at least five is highlighted by Remark 7, which notes that the existence of spanning 4-cycles breaks both the local-to-global argument in Section 3 and the local analysis in Section 4 <ref:2608.25491#pg7>. The authors suggest that spanning 4-cycles seem to be the only remaining hard gadgets for coloring <ref:2608. p. 5 6 Sol Ultra to work on triangle-free graphs with the Bochner identity,
but it did not find a proof after ≥ 20 hours. In fact, spanning 4-cycles seem to be the only remaining hard gadgets for coloring.Where the paper says it
Experimental Inspiration
The work was mainly inspired by recent research, specifically the use of GPT-5.6 Sol Ultra to simplify proofs involving Bochner identity and local gadgets, suggesting that this approach is particularly effective for proper vertex colorings <ref:2608. p. 5 These experiments also suggest that GPT is particularly effective at analyzing such local
gadgets. It was then natural to ask whether this method works for proper vertex colorings of
graphs of girth at least 5, where stars are again natural local gadgets. One advantage of our approach compared to those based on spectral independence (see e. [CLMM23]) is that the dependence of our mixing time on 1/δ is
polynomial, not exponential.Where the paper says it
Where the paper says it
Related Work
The paper relates its approach to various techniques including trickle-down methods and Bochner-type inequalities <ref:2608.25491#pg8>. The local-to-global theorem follows the same philosophy but uses an exact operator expansion and the girth-five geometry to collect every interacting pair of updates inside a closed star <ref:2608. p. 6 BŚ97, Żuk03, PR17, KM17, DK17, Par17, Opp18, KO20, Opp20, ALOV19, CGM21, AL20,
ALO20, GM20, FGYZ22, JPV22, CLV21, ALO21, AJK+22, KT26, AO23, GK23, AKV24,
CCC+25, LLO25, LO25]. Our local-to-global theorem follows the same philosophy,
but it uses an exact operator expansion and the girth-five geometry to collect every
interacting pair of updates inside a closed star.Where the paper says it
Anti-ferromagnetic Potts Model Details
For the anti-ferromagnetic Potts model, Theorem 3 provides specific bounds for tmix(ε) based on the interaction parameter β <ref:2608.25491#pg4>. The measure is irreducible when β > 0, and for proper coloring when β = 0, the condition q ≥ ∆ + 2 is required <ref:2608. p. 0 A Spectral Local-to-Global Principle for Spin
Systems on Graphs with Girth At Least Five
Xiaoyu Chen∗ Kuikui Liu†
Abstract
It is proved that, for every δ ∈ (0, 1), the Glauber dynamics for the uniform
distribution on proper q-colorings is rapidly mixing when q ≥ (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 local spectral contraction
condition, including the anti-ferromagnetic Potts model with q ≥ (1 + δ)(1 − β)∆.Where the paper says it
Final Bounds
The final mixing time bounds are derived by substituting the spectral gap estimate into the standard worst-start mixing bound <ref:2608.25491#pg4>. The resulting bounds are tmix(ε) = Oδ(n/2 log q + n log 1/ε), β = 0, and tmix(ε) = Oδ(n/2 log q + n 2∆ log 1/β + n log 1/ε), 0. p. 2 Let G = (V, E) be a finite simple graph on n vertices with
maximum degree ∆ and girth at least 5, and let q be an integer. If ∆ is sufficiently large in terms
of δ and
q ≥ (1 + δ)∆,
then the Glauber dynamics on proper vertex q-colorings is irreducible, has spectral gap Ωδ(1/n),
and satisfies
tmix(ε) = Oδ
n
2
log q + n log 1
ε
, ε ∈ (0, 1). A Spectral Local-to-Global Principle for Spin
Systems on Graphs with Girth At Least Five
Xiaoyu Chen∗ Kuikui Liu†
Abstract
It is proved that, for every δ ∈ (0, 1), the Glauber dynamics for the uniform
distribution on proper q-colorings is rapidly mixing when q ≥ (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 local spectral contraction
condition, including the anti-ferromagnetic Potts model with q ≥ (1 + δ)(1 − β)∆.Where the paper says it
Where the paper says it
Key Results Summary
The key findings are that the Glauber dynamics on proper q-colorings is rapidly mixing when q ≥ (1 + δ)∆ and the underlying graph has girth at least 5 <ref:2608.25491#pg4>. This result also extends to general multi-spin systems satisfying a local spectral contraction condition <ref:2608. p. 0 A Spectral Local-to-Global Principle for Spin
Systems on Graphs with Girth At Least Five
Xiaoyu Chen∗ Kuikui Liu†
Abstract
It is proved that, for every δ ∈ (0, 1), the Glauber dynamics for the uniform
distribution on proper q-colorings is rapidly mixing when q ≥ (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 local spectral contraction
condition, including the anti-ferromagnetic Potts model with q ≥ (1 + δ)(1 − β)∆. This
result also extends to general multi-spin systems satisfying a local spectral contraction
condition, including the anti-ferromagnetic Potts model with q ≥ (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.Where the paper says it
Where the paper says it
The anti-ferromagnetic Potts model is defined by µ(σ) ∝ β E where β = 1 gives a product distribution and β = 0 gives the uniform distribution on proper q-colorings <ref:2608.25491#pg5>. The generalization of Theorem 3 for the Potts model is proved in Section 6 <ref:2608. p. 3 In particular, when β = 1, µ becomes a product distribution; and when β = 0, µ is the
uniform distribution on proper q-colorings. The following generalization of Theorem 1
is proved for the Potts model. In particular, when β = 1, µ becomes a product distribution; and when β = 0, µ is the
uniform distribution on proper q-colorings. The following generalization of Theorem 1
is proved for the Potts model. With these proofs, we observe that the Bochner identity is useful for reducing a
global spectral-gap estimate to estimates on local gadgets:
• for Oppenheim’s trickle-down theorem, the local gadgets are codimension-2 links;
• for spectral independence via pairwise spectral influence, the local gadgets are
two-part links;
• for edge-coloring, the local gadgets are endpoint stars, which are cliques in the
corresponding line graph. These experiments also suggest that GPT is particularly effective at analyzing such local
gadgets. With these proofs, we observe that the Bochner identity is useful for reducing a
global spectral-gap estimate to estimates on local gadgets:
• for Oppenheim’s trickle-down theorem, the local gadgets are codimension-2 links;
• for spectral independence via pairwise spectral influence, the local gadgets are
two-part links;
• for edge-coloring, the local gadgets are endpoint stars, which are cliques in the
corresponding line graph. These experiments also suggest that GPT is particularly effective at analyzing such local
gadgets.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Local Contraction Condition
The local (α,ε)-spectral contraction condition requires that for every vertex v and every feasible pinning τ outside N[v], the marginals are α-bounded and there is an ε-contraction <ref:2608.25491#pg6>. This condition ensures that the spectral gap of the local dynamics is at least (1 − ηv)/2 <ref:2608. p. 0 A Spectral Local-to-Global Principle for Spin
Systems on Graphs with Girth At Least Five
Xiaoyu Chen∗ Kuikui Liu†
Abstract
It is proved that, for every δ ∈ (0, 1), the Glauber dynamics for the uniform
distribution on proper q-colorings is rapidly mixing when q ≥ (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 local spectral contraction
condition, including the anti-ferromagnetic Potts model with q ≥ (1 + δ)(1 − β)∆.Where the paper says it
Final Conclusion
The final conclusion is that the discrete-time Glauber dynamics has spectral gap Ωδ(1/n) <ref:2608.25491#pg4>. This result is proven by applying Theorem 5, which uses the local-to-global principle and Fourier analysis to establish a global spectral gap <ref:2608. p. 0 This
result also extends to general multi-spin systems satisfying a local spectral contraction
condition, including the anti-ferromagnetic Potts model with q ≥ (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. Let G = (V, E) be a finite simple graph on n vertices with
maximum degree ∆ and girth at least 5, and let q be an integer. If ∆ is sufficiently large in terms
of δ and
q ≥ (1 + δ)∆,
then the Glauber dynamics on proper vertex q-colorings is irreducible, has spectral gap Ωδ(1/n),
and satisfies
tmix(ε) = Oδ
n
2
log q + n log 1
ε
, ε ∈ (0, 1). A Spectral Local-to-Global Principle for Spin
Systems on Graphs with Girth At Least Five
Xiaoyu Chen∗ Kuikui Liu†
Abstract
It is proved that, for every δ ∈ (0, 1), the Glauber dynamics for the uniform
distribution on proper q-colorings is rapidly mixing when q ≥ (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 local spectral contraction
condition, including the anti-ferromagnetic Potts model with q ≥ (1 + δ)(1 − β)∆. A Spectral Local-to-Global Principle for Spin
Systems on Graphs with Girth At Least Five
Xiaoyu Chen∗ Kuikui Liu†
Abstract
It is proved that, for every δ ∈ (0, 1), the Glauber dynamics for the uniform
distribution on proper q-colorings is rapidly mixing when q ≥ (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 local spectral contraction
condition, including the anti-ferromagnetic Potts model with q ≥ (1 + δ)(1 − β)∆.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
References
The references listed include works on spectral independence, trickle-down methods, and Bochner-type inequalities <ref:2608.25491#pg8>. Specific references for the Potts model mixing bounds are [BBR25], [BBR26], [GJM+26], and others <ref:2608. p. 5 At positive temperature, early work used
Dobrushin-type and spatial-mixing arguments to establish rapid Glauber mixing, with
subsequent refinements for bounded-degree graphs and lattices [SS97, GJMP06]. Later
work developed correlation-decay and zero-free approaches to approximate counting [YZ15, BBR26, LSS25], clarified uniqueness and spatial mixing on trees [GGY18,
dBBR23, BdBBR23, CLMM23, BBR25], and obtained polynomial-time sampling on random regular and sparse random graphs [BGG+20, YZ16, Eft22]. At positive temperature, early work used
Dobrushin-type and spatial-mixing arguments to establish rapid Glauber mixing, with
subsequent refinements for bounded-degree graphs and lattices [SS97, GJMP06]. Later
work developed correlation-decay and zero-free approaches to approximate counting [YZ15, BBR26, LSS25], clarified uniqueness and spatial mixing on trees [GGY18,
dBBR23, BdBBR23, CLMM23, BBR25], and obtained polynomial-time sampling on random regular and sparse random graphs [BGG+20, YZ16, Eft22]. For general graphs of maximum degree ∆,
Jerrum proved optimal O(n log n) mixing for Glauber dynamics when q > 2∆ [Jer95]. The current state-of-the-art result is due to Carlson–Vigoda [CV25], who established
rapid mixing of a Markov chain known as the flip dynamics when q > C∆ for C ≈ 1. For general graphs of maximum degree ∆,
Jerrum proved optimal O(n log n) mixing for Glauber dynamics when q > 2∆ [Jer95]. The current state-of-the-art result is due to Carlson–Vigoda [CV25], who established
rapid mixing of a Markov chain known as the flip dynamics when q > C∆ for C ≈ 1. Supported by the NSF CAREER
grant CCF-2443045, and the Reed Fund at MIT. 1
arXiv:2608. Supported by the NSF CAREER
grant CCF-2443045, and the Reed Fund at MIT. 1
arXiv:2608. 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. 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. Trickle-down methods. Beginning with Garland’s method, local-to-global spectral
arguments propagate expansion from links to high-dimensional walks; this lineage
now includes local spectral expansion, spectral and entropic independence, and scalar,
matrix, partite, poset, localization, and C-Lorentzian trickle-down theorems [Gar73,
6 Beginning with Bochner’s identity and Bakry–Émery
theory, comparisons between a Dirichlet form and its iterated form have been used to
derive Poincaré and entropy-decay inequalities [Boc46, BÉ85, BGL14]. Discrete versions
were developed for finite Markov chains and interacting-particle systems [BCDP06,
CP07, Cap08, CDP09, DP13, Maa11, EM12, Mie13, EMT15, FM16, EHMT17, EF18], with
more recent extensions involving Beckner and curvature-dimension inequalities and
coupling-based curvature bounds [JY17, WZ21, Ped25].Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
The anti-ferromagnetic Potts model is defined by µG(σ) ∝ β E where β = 1 gives a product distribution and β = 0 gives the uniform distribution on proper q-colorings <ref:2608.25491#pg5>. The generalization of Theorem 3 for the Potts model is proved in Section 6 <ref:2608.25491#pg4>. The spectral gap estimate is uniform over all feasible pinnings τ <ref:2608.25491#pg4>. The paper proves the theorem for the anti-ferromagnetic Potts model <ref:2608.25491#pg4>.
The references listed include works on spectral independence, trickle-down methods, and Bochner-type inequalities <ref:2608.25491#pg8>. Specific references for the Potts model mixing bounds are [BBR25], [BBR26], [GJM+26], and others <ref:2608.25491#pg4>. The paper also cites foundational works on Markov chain mixing times <ref:2608.25491#pg4>. The work is supported by NSF grants CCF-2443045 and the Reed Fund at MIT <ref:2608.25491#pg2>. The paper was developed with interaction from GPT-5.6 Sol Ultra <ref:2608.25491#pg4>.
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Improved sampling of proper colorings on graphs with girth at least five. The system can sample from a uniform distribution on proper q-colorings with a mixing time of O delta to n/2 log q + n log 1 over epsilon, significantly improving efficiency compared to prior results that required higher girth or stricter degree constraints.
-
Rapid mixing for general multi-spin systems under local spectral contraction conditions. The improved system can rapidly mix when the underlying Gibbs distribution satisfies a local (alpha, epsilon)-spectral contraction condition, leading to a spectral gap of Omega alpha(1/n).
-
Enhanced analysis of continuous-time dynamics on star graphs using Fourier analysis. The system can utilize a novel Fourier analysis for continuous-time Glauber dynamics on stars to derive Poincaré inequalities with specific bounds related to the update rates eta v.
-
Application of the local-to-global principle to complex spin systems. The system can apply the new spectral local-to-global principle for girth five spin systems, extending its applicability beyond simple uniform distributions to general multi-spin systems satisfying a local spectral contraction condition.
-
Accelerated mixing for anti-ferromagnetic Potts models with varying interaction strength beta. The system can achieve rapid mixing for the anti-ferromagnetic q-state Potts model with an improved bound on mixing time: O delta to n/2 log q + n 2 delta log 1 over beta + n log 1 over epsilon, depending on whether beta is zero or positive.
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 at least (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 local spectral contraction condition, including the anti-ferromagnetic Potts model with q at least (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.
Sources
- On the spectral gap of the Kac walk and other binary collision processes
- Rapid Mixing on Random Regular Graphs beyond Uniqueness
- A simple proof of rapid mixing on random regular graphs beyond uniqueness
- Local-to-Global Contraction in Simplicial Complexes
- Approximating spin systems on planar graphs
- Sampling Colorings Close to the Maximum Degree: Non-Markovian Coupling and Local Uniformity
- Counting and Sampling Anti-ferromagnetic Potts Models on Random Regular Bipartite Graphs in the Non-uniqueness Regime
- Counterexamples to a Weitz-Style Reduction for Multispin Systems
- Trickle-down Theorems via C-Lorentzian Polynomials II: Pairwise Spectral Influence and Improved Dobrushin's Condition
- Spatial mixing and approximate counting for Potts model on graphs with bounded average degree
Related papers
- Exploiting Low Scanwidth to Resolve Soft Polytomies
- PHastR: Faster Minimal Perfect Hashing with Rotated Layouts
- Fine-Grained Complexity of Approximating Vector Knapsack: A Faster Algorithm and Equivalence with k-SUM in 2D
- Polynomial-time computation of p-contraction fixed points for even p
- Separations Between Submodular-Like Graph Widths
- Bounded Integer Programming in Almost N 2d Time