q-colourability threshold of G(n, d/n) exists, says a machine-written paper
Awaiting review
Importance: major (4 of 5)The takeaway
Achlioptas and Friedgut proved in 1999 that q-colourability of the random graph G(n, d/n) has a sharp threshold, but only along a sequence that might depend on n. Whether that sequence converges to a constant d_q was recorded as an open problem and is widely called well known. On 29 Oct P. M. Aronow (Yale) and Patrick Lopatto (UNC Chapel Hill) posted on Hexagon a proof that it converges for every q ≥ 3, with a window of O(n(log n)^(−3/2)) steps for the hitting time. The authors’ note says the whole document except that note is machine-written. The provenance names Opus 5.5, GPT 6 Astra, GPT Luna 6 and GPT 6.1 Sol, and says the results were formalised in Lean, but the paper links no Lean repository. Human understanding: ‘some parts’. Two companion papers on the dynamics of the spherical Sherrington–Kirkpatrick model came the same day.
Status
- Claim
Awaiting review
- Our reporting
- Medium confidence
- Verification
- Lean-verified
- Importance
- Major (4 of 5)
- Last verified
- 29 October 2026
Your AI and this story
- GPT-6 Astra182 days after its cutoff
- Claude Opus 5.5121 days after its cutoff
- Gemini 4 Argon212 days after its cutoff
- Grok 4.7151 days after its cutoff
None of these four assistants can know about it. The closest, Claude Opus 5.5, stops 121 days before it.
Key facts
- Claim (abstract, verbatim): ‘We prove that there exists d_q > 0 such that the random graph on n vertices with independent edge probability d/n is q-colorable with probability tending to one for fixed 0 ≤ d < d_q and to zero for fixed d > d_q, as n → ∞.’ Also: the first loss of colourability under random edge additions lies, with probability ≥ 1 − ε, in a deterministic window of O_{q,ε}(n(log n)^(−3/2)) steps
- Background (paper): Achlioptas and Friedgut proved a sharp threshold along a sequence d̂_n and ‘recorded its convergence as an open problem’; Achlioptas and Molloy noted it was ‘widely conjectured’; later works call it ‘a well-known open problem’. Known 3-colouring bounds: colourable for d ≤ 4.03, not for d > 4.697. The proof does not need the Achlioptas–Friedgut theorem
- Authors’ note (verbatim): ‘With the exception of these notes, the entire document is machine-written. We have carefully supervised its preparation to ensure that the proofs are readable and that previous literature is appropriately cited.’ A ‘more carefully written version’ is in preparation for journal submission
- Provenance (Hexagon, verbatim): ‘Proof discovery and verification were done with a combination of Opus 5.5, GPT 6 Astra, GPT Luna 6, and GPT 6.1 Sol. The results were formalized in Lean 4 by Opus 5.5, Luna 6, and GPT Sol 6.1. The writing was done by Opus 5.5, GPT 6.1 Sol, and Astra 6.’ Text ‘primarily AI-generated’; human understanding ‘some parts’
- Builds on OpenAI release preprints cited in the paper: ‘A limiting satisfiability threshold for every fixed clause size’ (its deletion argument) and ‘A sharp threshold bound for monotone graph properties’; compare the random k-SAT entry
- Same day, same pair: ‘Dynamics of the spherical Sherrington–Kirkpatrick model’ Parts I–II (Hexagon 2610.00609, 2610.00610), the asymptotic total-variation distance to equilibrium of Langevin dynamics, with cutoff and a Gaussian profile for β < β_c = 1/√2; also machine-written with the same models and Lean claims
- Verification status: unrefereed Hexagon preprint; Lean formalization claimed in the provenance but no repository or Palomar entry linked in the paper; no expert reaction or HN thread found on 29 Oct. The pair’s 26 Oct five-paper 3D Yang–Mills claim is likewise unchecked
What happened
The chromatic number of sparse random graphs goes back to Erdős and Rényi. For q-colourability, Achlioptas and Friedgut showed in 1999 that the transition is sharp, but their threshold was a sequence d̂_n that could in principle oscillate. Whether it converges has been an open problem since then. It is the colouring analogue of the random k-SAT threshold question, which Ding, Sly and Sun settled for large k.
On 29 Oct Aronow and Lopatto posted a proof of convergence for every q ≥ 3. They say the document is machine-written and that they supervised it for readability and citations. The provenance names four models for discovery, verification and writing, and three for a Lean formalization that the paper does not link. The argument cites OpenAI’s September release preprints on the random k-SAT threshold.
Why it matters
The question is classic in probabilistic combinatorics and appears in surveys as open. The claim joins the AI-generated random k-SAT threshold proofs of October and the same pair’s Yang–Mills papers. Until the Lean files are public or a specialist reads the proof, it is a claim.
What is disputed or not yet verified
| Verification | Unrefereed Hexagon preprint; Lean formalization claimed, not linked |
|---|
Sources
3 sources from 1 site. Numbers match the chips in the text.
3 sources: 3 primary
Primary
- Hexagon 2610.00608: Existence of the q-Colorability Threshold for Sparse Random Graphs (Aronow, Lopatto)hexagonmath.org, paper
- Hexagon 2610.00609: Dynamics of the spherical SK model, Part Ihexagonmath.org, paper
- Hexagon 2610.00610: Dynamics of the spherical SK model, Part IIhexagonmath.org, paper
Changes
- Filed (Hexagon API records and PDF of 2610.00608, records of 2610.00609–00610; HN search found no thread)