VibeMathedMath problems solved with AI

Rapid mixing of Glauber dynamics for colorings of G(n,d/n)G(n,d/n) in the uniqueness regime

Let G∼G(n,d/n)G\sim G(n,d/n) be a sparse Erdős-Rényi random graph with fixed average degree dd. Is the single-site Glauber dynamics on proper qq-colorings of GG rapidly mixing, with high probability over GG, for every qq in the tree uniqueness regime, that is for q≥d+2q\ge d+2? Efthymiou, Hayes, Stefankovic and Vigoda record this as the prediction from statistical physics (Krzakala et al.) and proved rapid mixing for q>αdq>\alpha d, α≈1.7632\alpha\approx1.7632, for large dd.

Result
Proved(see note)
Status
Partial result
AI contribution
AI co-developed
Method
Argument
Field
Markov chain mixing, random graphs
Posed by
Efthymiou, Hayes, Stefankovic and Vigoda, recording a prediction of Krzakala, Montanari, Ricci-Tersenghi, Semerjian and Zdeborova (2007)
Year posed
2017
Years open
9y
Solved
2026-11-09
Model
GPT-5.6 Sol; GPT-6.1 Sol
Vendor
OpenAI
Collaborators
Leon Schiller
Verification
Unreviewed
Publication
Preprint
Significance
24 / 100
Disclosed cost
—
Wikipedia
No dedicated article

What was actually shown

Theorem 1.1: for every 0<ε≤1/20<\varepsilon\le 1/2, all sufficiently large dd and all integers q≥d+d1/2+εq\ge d+d^{1/2+\varepsilon}, with probability 1−o(1)1-o(1) over G∼G(n,d/n)G\sim G(n,d/n) the Glauber dynamics for proper qq-colorings has τmix(δ)=Od,ε(n2+ζ(1+log⁡(1/δ)))\tau_{\mathrm{mix}}(\delta)=O_{d,\varepsilon}\big(n^{2+\zeta}(1+\log(1/\delta))\big) with ζ=Cεlog⁡q/dε\zeta=C_\varepsilon\log q/d^{\varepsilon}. This improves q>1.763dq>1.763d (EHSV 2018). Three weeks earlier Li and Yang (arXiv 2610.25391, also AI-assisted) proved polynomial mixing for q≥(1+od(1))dq\ge(1+o_d(1))d; the present paper gives an explicit surplus d1/2+εd^{1/2+\varepsilon} and a near-quadratic mixing time. Partial: large dd only, and q=d+2q=d+2 is not reached.

What the AI did

From the paper's AI disclosure (Section 1.4): the main ideas of the proofs were developed using long interactions with GPT-5.6 Sol and GPT-6.1 Sol, after instructing it to devise a Bochner-type inequality for block dynamics for proper colorings. The same models assisted with writing. The author states that all claims and calculations were independently verified by him and takes full responsibility.

Verification

No independent mathematician has checked this yet. Checked here on 15 November 2026: Theorem 1.1 of arXiv 2611.12444v1 (Leon Schiller, Hasso Plattner Institute) read and matches the result note; the AI disclosure is in the paper itself (Section 1.4). The posed question was traced to Efthymiou, Hayes, Stefankovic and Vigoda (arXiv 1707.03796), who state that rapid mixing is conjectured throughout the uniqueness region, so for q at least d+2, citing Krzakala et al. (PNAS 2007). Li and Yang (arXiv 2610.25391, 18 October 2026) had already proved rapid mixing for q at least (1+o(1))d, also with GPT models disclosed; the author calls the two works concurrent and independent, and this one is quantitatively stronger. The proof (about 55 pages) was not checked here. Partial because only large d is covered and the colour surplus above d still grows with d.

Sources

Submitted by MellowGander562 on

Changelog2 changes

Discussion