Rapid mixing of colouring and antiferromagnetic Potts dynamics on high-girth graphs
Follow the latest progress by email.
For finite simple n-vertex graphs of maximum degree Δ and girth at least five, how quickly does proper-q-colouring Glauber dynamics mix when q is near Δ? The stated near-Δ target uses q≥(1+δ)Δ for fixed δ∈(0,1) and sufficiently large Δ, with gap Ωδ(1/n) and mixing time Oδ(n² log q+n log(1/ε)).
Why it matters and what counts as progress
Why it matters: It seeks efficient sampling under weaker local cycle restrictions. The exact q≥Δ+2 threshold and uniformly optimal O(n log n) time are stronger targets.
What counts as progress: Lower the colouring threshold or girth requirement with quantitative mixing bounds. Reaching q≥Δ+2 or O(n log n) mixing would strengthen the present target.
How the problem developed
- 1995 · Partial result [1]
Mark Jerrum Proved rapid Glauber mixing for general graphs when q > 2Δ; the threshold left a gap near the colourability limit q = Δ + 2.
- 2013 · Partial result [1]
Dyer, Frieze, Hayes, and Vigoda Obtained near-optimal Glauber mixing thresholds for high-girth graphs, with separate thresholds for girth at least five and at least seven.
- 26 Aug 2026 · Reported claim [1]
Xiaoyu Chen and Kuikui Liu; GPT-5.6 Sol Ultra The preprint claims rapid Glauber mixing for proper q-colourings on graphs of girth at least five when q ≥ (1+δ)Δ, and extends the local-to-global method to multi-spin systems including antiferromagnetic Potts models.
AI contribution
A Spectral Local-to-Global Principle for Spin Systems on Graphs with Girth At Least Five
For each δ∈(0,1), sufficiently large maximum degree Δ and finite simple n-vertex graphs of girth at least 5, Theorem 1 gives irreducible proper-q-coloring Glauber dynamics with spectral gap Ωδ(1/n) and mixing time Oδ(n² log q+n log(1/ε)) when q≥(1+δ)Δ. Theorem 3 extends the method to antiferromagnetic Potts models under its stated β and q conditions; Theorem 5 gives a local spectral-contraction criterion for general multi-spin systems. The result is rapid mixing, not the conjectured exact q≥Δ+2 threshold or uniformly optimal O(n log n) bound.
Sources
Website timeline
Publication dates and editorial changes.