Colourings Glauber dynamics above (1+1/e)Δ (GPT-6 Astra Pro)
Awaiting review
Importance: major (4 of 5)Status
- Claim
Awaiting review
- Our reporting
- Medium confidence
- Verification
- Preprint only
- Importance
- Major (4 of 5)
- Last verified
- 4 November 2026
Your AI and this story
- GPT-6 Astra188 days after its cutoff
- Claude Opus 5.5127 days after its cutoff
- Gemini 4 Argon218 days after its cutoff
- Grok 4.7157 days after its cutoff
None of these four assistants can know about it. The closest, Claude Opus 5.5, stops 127 days before it.
Key facts
- Claim: for every γ > 0 and sufficiently large Δ, spectral gap Ω_γ(1/n) and mixing time O_γ(n² log q) when q ≥ (1+1/e+γ)Δ
- 1+1/e comes from the hard-core uniqueness threshold ≈ e/Δ on the infinite Δ-regular tree; proof via a Bochner-type inequality using ‘hidden hard-core models’ in the colour classes
- Context: the conjecture is rapid mixing for q ≥ Δ+2; for general graphs the known threshold had stayed close to 11/6 Δ since Vigoda (1999)
- Disclosure: ‘The main ideas of this paper emerged from extensive discussions with ChatGPT-6 Astra Pro. ChatGPT-6 Astra Pro also suggested that a finer analysis … should improve the constant 1 + 1/e further … All mathematical claims have been independently verified by the author’
- Verification: preprint; no expert comment or HN thread found on 4 Nov
What happened
A single-author preprint posted on 3 Nov 2026 claims a large improvement on one of the best-known problems in sampling: when Glauber dynamics for random proper colourings mixes fast on every graph of maximum degree Δ. The claimed threshold (1+1/e)Δ ≈ 1.368Δ (for large Δ) would replace general-graph bounds that had stayed near 1.8Δ for over 25 years. The paper credits ChatGPT-6 Astra Pro with the main ideas and says the author simplified the arguments and checked all claims.
Why it matters
If it holds, this is a major step towards the Δ+2 conjecture, and another case of a frontier model supplying the central idea of a theoretical computer science result. Status is unverified: no specialist reading has appeared yet.
What is disputed or not yet verified
| Verification | Unrefereed preprint |
|---|
Sources
1 source from 1 site. Numbers match the chips in the text.
1 source: 1 primary
Primary
Changes
- Filed from the arXiv PDF