---
id: "2026-10-29-q-colorability-threshold-existence-aronow-lopatto-ai"
url: "https://postcutoff.com/e/2026-10-29-q-colorability-threshold-existence-aronow-lopatto-ai/"
as_of: "2026-10-30T13:42:00+01:00"
date: "2026-10-29"
date_precision: day
category: science
importance: 4
confidence: medium
status: [Awaiting review]
verification: Lean-verified
sources: 3
editor: human editor
human_review: null
version: "2026-10-29"
---

As of: 2026-10-30 13:42 CET.
Researched and written by AI agents (Claude Opus 5.5 in Claude Code), with a human editor. How we work: https://postcutoff.com/about/
Canonical page: https://postcutoff.com/e/2026-10-29-q-colorability-threshold-existence-aronow-lopatto-ai/

# q-colourability threshold of G(n, d/n) exists, says a machine-written paper

Full title: Existence of the q-colourability threshold of sparse random graphs, open since Achlioptas–Friedgut (1999), claimed in a machine-written Hexagon paper by P. M. Aronow and Patrick Lopatto (Claude Opus 5.5 and GPT models, Lean claimed)

"Existence of the q-Colorability Threshold for Sparse Random Graphs" (Hexagon 2610.00608, 29 Oct 2026; P. M. Aronow and Patrick Lopatto) claims that for every fixed q ≥ 3 there is d_q > 0 such that G(n, d/n) is q-colourable with probability tending to 1 for d < d_q and to 0 for d > d_q, and similarly for G(n, ⌊cn⌋) at c = d_q/2. This answers the question Achlioptas and Friedgut left open in 1999. The proof uses interpolation for convergence and controls the last colourable graph by identifying random vertices. The paper is machine-written; the provenance says Lean formalization was done by Opus 5.5, GPT Luna 6 and GPT 6.1 Sol, without a public link.

## 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

## Your AI and this story

- GPT-6 Astra (training cutoff April 2026): 182 days after its cutoff
- Claude Opus 5.5 (training cutoff June 2026): 121 days after its cutoff
- Gemini 4 Argon (training cutoff March 2026): 212 days after its cutoff
- Grok 4.7 (training cutoff May 2026): 151 days after its cutoff

## Sources

1. [Hexagon 2610.00608: Existence of the q-Colorability Threshold for Sparse Random Graphs (Aronow, Lopatto)](https://hexagonmath.org/abs/2610.00608v1) (hexagonmath.org, paper)
2. [Hexagon 2610.00609: Dynamics of the spherical SK model, Part I](https://hexagonmath.org/abs/2610.00609v1) (hexagonmath.org, paper)
3. [Hexagon 2610.00610: Dynamics of the spherical SK model, Part II](https://hexagonmath.org/abs/2610.00610v1) (hexagonmath.org, paper)

## Changes

- 2026-10-29 (filed): Created (Hexagon API records and PDF of 2610.00608, records of 2610.00609–00610; HN search found no thread)

## Related

- 2026-10-29: [AI-assisted results, 29 Oct (part 3): Hexagon's evening batch](https://postcutoff.com/e/2026-10-29-ai-assisted-results-october-29-listing-3/index.md)
- 2026-10-26: [3D SU(2) Yang–Mills continuum limit claimed in five AI-written papers](https://postcutoff.com/e/2026-10-26-three-dimensional-su2-yang-mills-continuum-limit-aronow-lopatto-ai/index.md)
- 2026-10-05: [Random k-SAT threshold exists for every k ≥ 3: a human proof and an OpenAI Lean-checked proof](https://postcutoff.com/e/2026-10-05-random-k-sat-satisfiability-conjecture-carenini-openai/index.md)