Rapid mixing of Glauber dynamics for colorings of in the uniqueness regime
Let be a sparse Erdős-Rényi random graph with fixed average degree . Is the single-site Glauber dynamics on proper -colorings of rapidly mixing, with high probability over , for every in the tree uniqueness regime, that is for ? Efthymiou, Hayes, Stefankovic and Vigoda record this as the prediction from statistical physics (Krzakala et al.) and proved rapid mixing for , , for large .
- 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 , all sufficiently large and all integers , with probability over the Glauber dynamics for proper -colorings has with . This improves (EHSV 2018). Three weeks earlier Li and Yang (arXiv 2610.25391, also AI-assisted) proved polynomial mixing for ; the present paper gives an explicit surplus and a near-quadratic mixing time. Partial: large only, and 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