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

arXiv:2608.25491 · cs.DS, cs.DM, math.PR · Submitted 2026-08-26 · Read on arXiv

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

Where the paper says it

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 − β)∆.

25491/pg3.

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

Where the paper says it

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).

25491#pg8>. The main ideas behind all the proofs were developed through several rounds of interaction with GPT-5. p. 0
Where the paper says it

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 <ref:2608. p. 0
Where the paper says it

The main ideas behind all the proofs were developed through several rounds of interaction with GPT-5. 6 Sol Ultra.

p. 0
Where the paper says it

The main ideas behind all the proofs were developed through several rounds of interaction with GPT-5. 6 Sol Ultra.

p. 0
Where the paper says it

The main ideas behind all the proofs were developed through several rounds of interaction with GPT-5. 6 Sol Ultra.

25491#pg4>.

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

Where the paper says it

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.

25491#pg14>. This leads to a discrete-time spectral gap of at least ε/(4n) <ref:2608. p. 6
Where the paper says it

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].

25491#pg20>.

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

Where the paper says it

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.

25491#pg15>. Theorem 25 provides a Poincaré inequality for this system with parameter η <ref:2608. p. 9
Where the paper says it

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.

25491#pg16>.

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

Where the paper says it

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.

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

Where the paper says it

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.

25491#pg19>.

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

Where the paper says it

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.

25491#pg18>.

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

Where the paper says it

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.

25491#pg8>.

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

Where the paper says it

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.

25491#pg13>. The authors also note that the dependence of their mixing time on 1/δ is polynomial, not exponential <ref:2608. p. 3
Where the paper says it

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.

25491#pg5>.

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

Where the paper says it

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.

25491#pg8>.

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

Where the paper says it

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 − β)∆.

25491#pg4>.

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

Where the paper says it

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).

The paper concludes by proving the theorem for the anti-ferromagnetic Potts model <ref:2608. p. 0
Where the paper says it

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 − β)∆.

25491#pg4>.

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

Where the paper says it

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 − β)∆.

25491#pg4>. The 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 <ref:2608. p. 0
Where the paper says it

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.

25491#pg4>.

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

Where the paper says it

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.

p. 3
Where the paper says it

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.

25491#pg4>. The spectral gap estimate is uniform over all feasible pinnings τ <ref:2608. p. 5
Where the paper says it

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.

p. 5
Where the paper says it

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.

25491#pg4>.

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

Where the paper says it

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 − β)∆.

25491#pg4>.

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

Where the paper says it

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.

25491#pg4>. The overall mixing time 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
Where the paper says it

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).

The paper proves the theorem for the anti-ferromagnetic Potts model <ref:2608. p. 0
Where the paper says it

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 − β)∆.

p. 0
Where the paper says it

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 − β)∆.

25491#pg4>.

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

Where the paper says it

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].

p. 5
Where the paper says it

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].

25491#pg4>. The paper also cites foundational works on Markov chain mixing times <ref:2608. p. 2
Where the paper says it

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.

p. 2
Where the paper says it

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.

25491#pg4>. The work is supported by NSF grants CCF-2443045 and the Reed Fund at MIT <ref:2608. p. 0
Where the paper says it

Supported by the NSF CAREER grant CCF-2443045, and the Reed Fund at MIT. 1 arXiv:2608.

p. 0
Where the paper says it

Supported by the NSF CAREER grant CCF-2443045, and the Reed Fund at MIT. 1 arXiv:2608.

25491#pg2>. The paper was developed with interaction from GPT-5. p. 0
Where the paper says it

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.

p. 0
Where the paper says it

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 <ref:2608.25491#pg4>. The references also include works on spectral independence [AJK+24], trickle-down theorems [ALO20], and C-lorentzian polynomials <ref:2608. p. 5
Where the paper says it

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

25491#pg8>. The paper also includes work on Ricci curvature bounds <ref:2608. p. 6
Where the paper says it

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].

25491#pg8>.

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

  1. 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.

  2. 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).

  3. 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.

  4. 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.

  5. 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

Related papers