Grid-minor exponent 6 in polynomial time (Hajiaghayi with Astra)
Awaiting review
The takeaway
Robertson and Seymour’s grid-minor theorem is central to graph minors and bidimensionality; Chuzhoy and Tan’s g⁹ bound (2021) was the best. Two AI-assisted claims now go below it: Édouard Bonnet’s Lean-checked g⁸·polylog with Codex, and Hajiaghayi’s g⁶·polylog with a polynomial-time algorithm, developed with OpenAI Astra.
Status
- Claim
Awaiting review
- Our reporting
- Medium confidence
- Verification
- Lean-verified
- Importance
- 3 of 5
- Last verified
- 13 November 2026
Your AI and this story
- GPT-6 Astra196 days after its cutoff
- Claude Opus 5.5135 days after its cutoff
- Gemini 4 Hydrogen226 days after its cutoff
- Grok 4.7165 days after its cutoff
None of these four assistants can know about it. The closest, Claude Opus 5.5, stops 135 days before it.
Key facts
- Claim (abstract): ‘Every graph whose treewidth is at least g⁶ times a fixed polylogarithmic factor contains a g×g grid minor that our randomized algorithm finds with constant probability. The algorithm outputs an explicit minor model, and the exponent in its running time is independent of g.’
- Prior bounds: Robertson–Seymour (1986) exponential; Chekuri–Chuzhoy (2016) polynomial, g⁹⁸ threshold in their polynomial-time construction; Chuzhoy–Tan (2021) g⁹·polylog existence; known lower bound g² log g
- AI Use Statement (verbatim): ‘This work resulted from extensive interaction between the author and OpenAI Astra, with the author providing suggestions and critically checking Astra’s responses through iterative exchanges. OpenAI Astra was also used in writing and revising the manuscript through detailed prompts from the author, with Gemini Argon assisting in some parts.’ A GitHub link (hajiaghayi/Grid-Minor) is announced
- Lax Lean Archive lax-17 (Édouard Bonnet, with Codex 5.5 and Codex 5.6 credited as formalizers): treewidth ≥ K·g⁸·(log g)^b forces a g×g grid minor, via ‘a logarithmic-depth amortized controller’ for Chuzhoy–Tan’s recursive slicing; the abstract says the combinatorial producers, controller, numerical inequalities and final composition ‘are checked in Lean’; running time not covered; registered 2 Aug 2026, no reviews or flags listed
- Status: exponent 6 is an unrefereed preprint with no formal proof; exponent 8 is Lean-checked per the archive page; neither has expert commentary found by 13 Nov
What happened
On 12 Nov 2026 Mohammad Hajiaghayi (University of Maryland) posted a preprint claiming a sixth-power excluded-grid theorem with a polynomial-time algorithm that outputs the grid minor. He states the work came from an extended exchange with OpenAI’s Astra, which also helped write the paper, with Gemini Argon in some parts. The paper cites an exponent-8 bound by Édouard Bonnet, formalized in Lean with OpenAI’s Codex and posted on the Lax Lean Archive, a site that lists Lean-checked submissions.
Why it matters
Quantitative grid-minor bounds drive the running times of many algorithms on sparse graphs (bidimensionality). Going from g⁹ to g⁶ would be a large step, but it is an unrefereed claim; the exponent-8 result has a Lean check but no published human review.
What is disputed or not yet verified
| Verification | Preprint (exponent 6); Lean-checked on the Lax Lean Archive (exponent 8) |
|---|
Sources
3 sources from 2 sites. Numbers match the chips in the text.
3 sources: 3 primary
Primary
Changes
- Filed (science agent; arXiv PDF and the lax-17 page read)