Rapid mixing for spin systems on graphs of girth at least five

It is proved that, for every $\delta\in(0,1)$ , the Glauber dynamics for the uniform distribution on proper $q$ -colorings is rapidly mixing when $q\geq(1+\delta)\Delta$ and the underlying graph has girth at least $5$ and maximum degree $\Delta=\Omega_{\delta}(1)$ . This result also extends to general multi-spin systems satisfying a local spectral contraction condition, including the anti-ferromagnetic Potts model with $q\geq(1+\delta)(1-\beta)\Delta$ .

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.

Result: Proved(see note)
Status: Partial result
AI contribution: AI co-developed
Method: Argument
Field: Glauber dynamics
Posed by: Mark Jerrum
Year posed: 1995
Years open: 31y
Solved: 2026-08-26
Model: GPT-5.6 Sol Ultra
Vendor: OpenAI
Collaborators: Xiaoyu Chen, Kuikui Liu
Verification: Unreviewed
Publication: Preprint
Significance: 30 / 100
Disclosed cost: —
Wikipedia: No dedicated article

What was actually shown

For fixed $\delta\in(0,1)$ and all sufficiently large $\Delta$ depending only on $\delta$ , Glauber dynamics for proper $q$ -colorings mixes rapidly on every graph of girth at least $5$ whenever $q\ge(1+\delta)\Delta$ : spectral gap $\Omega_\delta(1/n)$ and $t_{\mathrm{mix}}(\varepsilon)=O_\delta(n^2\log q+n\log(1/\varepsilon))$ . An analogous theorem holds for the anti-ferromagnetic Potts model at $q\ge(1+\delta)(1-\beta)\Delta$ .

What it does and does not improve. On girth it is a large gain: previous results near the $(1+\delta)\Delta$ threshold needed girth at least eleven (Hayes-Vigoda, extended to constant degrees by Jain-Mizgerd-Vigoda). On the mixing rate it is weaker - those give optimal $O(n\log n)$ , this gives $O(n^2\log q)$ . It does not touch the folklore conjecture that mixing is rapid on every graph for $q\ge\Delta+2$ ; Remark 7 names spanning 4-cycles as the obstruction.

What the AI did

From the paper's section 1.2, "Discussions about experiments with AI". The authors first asked GPT-5.6 Sol Ultra to redo several known trickle-down results via the Bochner identity, and drew the pattern themselves: "With these proofs, we observe that the Bochner identity is useful for reducing a global spectral-gap estimate to estimates on local gadgets." They then brought the girth-5 colorings question to the model, "which proposed an affirmative proof strategy. The human authors then verified the argument, generalized the proof with further assistance from GPT, and streamlined the paper." GPT-5.6 was also used for exposition and typographical checking. The abstract's own framing is "several rounds of interaction", which is why this is co-developed rather than AI-discovered: the model supplied the strategy for the main theorem inside a frame the humans built and after an observation they made.

The paper also records where the model failed, which is rare enough to note. Remark 7: "We asked GPT-5.6 Sol Ultra to work on triangle-free graphs with the Bochner identity, but it did not find a proof after $\sim$ 20 hours." The authors add that the model claims a proof generalizing the theorem to all graphs without spanning 4-cycles, which they deliberately left out "since we did not find any new ideas in it".

Verification

An arXiv preprint (v1, 26 August 2026, cs.DS), unrefereed, with no formalization and no computational certificate, so nothing here was mechanically checkable and no mathematics was checked. Verified on 27 August 2026: the paper exists at arXiv:2608.25491 with the title and both authors this entry lists; the statement and the quantitative claims above are its abstract and Theorem 1; the AI disclosure appears in the abstract and in section 1.2, quoted above; and the prior work is correctly characterised - Jerrum 1995 for the folklore conjecture and the $q>2\Delta$ result, Hayes-Vigoda 2003 for the girth-eleven regime, Jain-Mizgerd-Vigoda for its extension to constant degree, and Carlson-Vigoda for the current $1.809\Delta$ state of the art on general graphs.

Source

PaperarXiv

Submitted by VibeGene on 27 Aug 2026