GPT-6 Astra finds a proof improving the Kővári–Sós–Turán bound: diagonal bipartite Ramsey numbers b(t,t) = O(2^t) (Mubayi)
On Sept 26, 2026 Dhruv Mubayi posted a proof that every bipartite graph with N vertices per side and at least N²/2 edges contains K_{t,t} once N ≥ c·2^t. That improves the classical Kővári–Sós–Turán requirement of order t·2^t and cuts the diagonal bipartite Ramsey upper bound from Conlon's O(2^t log t) to O(2^t). The abstract says "The proof was found by GPT-6 Astra": an 8-page proof the author first found incomprehensible and then rewrote with the model.
Key facts
- arXiv 2609.32937 (math.CO), Dhruv Mubayi, 'Sharper Zarankiewicz and Diagonal Bipartite Ramsey Bounds', Sept 26, 2026
- Result: density ≥ 1/2 bipartite graphs contain K_{t,t} when N ≥ c·2^t; hence b(t,t) = O(2^t), improving Conlon's O(2^t log t)
- AI declaration: 'The proof of the main result was found by GPT-6 Astra after several guided prompts by the author. Astra first produced a proof that was only 8 pages long and was incomprehensible to the author'; later write-ups are largely the author's
- Mubayi had earlier prompted Astra to extensions of the Erdős–Sós work (see 2026-09-03-erdos-sos-conjecture-proved-gpt-6-astra)
Science result
- Field
- mathematics / extremal graph theory / Ramsey theory
- Problem
- Zarankiewicz problem at density 1/2 and diagonal bipartite Ramsey numbers b(t,t)
- Result
- b(t,t) = O(2^t); K_{t,t} guaranteed in balanced bipartite graphs of density 1/2 once N ≥ c·2^t.
- AI system
- GPT-6 Astra
- Human role
- AI-found proof after guided prompting; human rewrote and takes responsibility
- Verification
- Unrefereed preprint
- Status
- pending
What happened
Mubayi, a leading extremal combinatorialist, reports that GPT-6 Astra found a proof removing the log factor from the best bound on diagonal bipartite Ramsey numbers. The improvement over the 1954 Kővári–Sós–Turán counting bound comes from a new method that he says "will probably have further applications".
Why it matters
It is a quantitative improvement on a classical bound in a central area, credited outright to a model in the abstract. That kind of disclosure was rare before September 2026.
Changelog
- 2026-10-01: created (leads run, 07:40 completion)
Related events
- GPT-6 Astra proves the Erdős–Sós conjecture (1962) with a short counting argument; mathematicians race to simplify and extend it ★★★★★
- Summer 2026 flood: dozens of named conjectures settled on arXiv with disclosed AI help (July–September catalogue) ★★★★
- Chvátal's 1972 conjecture proved (Chang–Liu–Liu, ChatGPT-assisted), then a GPT-6 Astra 'proof from The Book' and a Codex-built Lean formalization ★★★★
Sources (1)
id: 2026-09-26-mubayi-zarankiewicz-astra · updated 2026-10-01 · open in the interactive timeline