Borodin–Kostochka conjecture claimed for maximum degree ≥ 4583 (down from 5.3 million), then ≥ 1000 (26 Oct), with GPT-6 Astra assisting
Awaiting review
The takeaway
A preprint posted on Zenodo on Oct 20, 2026 by Lizhong Chen (HKUST) claims the Borodin–Kostochka conjecture (1977) for every graph of maximum degree Δ ≥ 4583: χ ≤ max{ω, Δ − 1}.
Status
- Claim
Awaiting review
- Our reporting
- Medium confidence
- Verification
- Preprint only
- Importance
- 3 of 5
- Last verified
- 26 October 2026
Your AI and this story
- GPT-6 Astra173 days after its cutoff
- Claude Opus 5.5112 days after its cutoff
- Gemini 4 Argon203 days after its cutoff
- Grok 4.7142 days after its cutoff
None of these four assistants can know about it. The closest, Claude Opus 5.5, stops 112 days before it.
Key facts
- Update 26 Oct 2026: a new Zenodo record by the same author, ‘The Borodin–Kostochka inequality from degree 1000’ (40 pp.), lowers the claimed threshold to Δ ≥ 1000. Its computer-assisted part uses ‘rational and outward-rounded arithmetic, giving a computer-assisted proof with no restriction on the order of the graph’. AI disclosure (verbatim, excerpt): ‘OpenAI GPT-6 Astra was used to assist with the computational programs, certificate review, literature organisation, and English drafting and editing. AI assistance also contributed to the development and exposition of several parts of the mathematical argument’ (Sections 4–6, Appendix B). Still unrefereed; open for 9 ≤ Δ < 1000
- Conjecture (Borodin & Kostochka, JCTB 1977): every graph with Δ ≥ 9 has χ ≤ max{ω, Δ − 1}, one colour fewer than Brooks’s theorem when there is no clique of size Δ
- Earlier: Reed proved it for sufficiently large Δ (JCTB 1999); Liu, Sun, Wang and Zeng gave the explicit threshold 5.3 × 10⁶ (arXiv 2603.16670, v3 May 2026); Chen’s own SSRN working manuscript had 2.9 × 10⁶
- New claim: Δ ≥ 4583, about a thousandfold lower; method: clique/sparse decomposition, random partial colouring with pre-selected families of witness triples, two applications of the local lemma, finite exponential-moment bounds
- The numerical part checks finitely many scalar inequalities in exact rational arithmetic (no graph enumeration); programs, parameters and reference output accompany the paper
- Disclosure (verbatim): ‘OpenAI GPT-6 Astra assisted with the resampling estimates in Section 6.4, moment-bound optimisation in Sections 7.3 and 8.1, weighted selection and local-lemma parameter choices in Sections 5 and 9, and the small-deficit constructions in Appendix A.3.’
- Single author; ~22,800-word PDF; no Lean formalisation; no expert reaction found on Oct 20
What happened
The paper does not settle the conjecture, but it claims to move the explicit bound from millions to a few thousand. The AI’s role is stated precisely in the paper’s own declaration (above). It was posted on Zenodo, not arXiv, and found through the sweep’s Zenodo step; its PDF was read for the disclosure.
Why it matters
It is another case of a frontier model credited with the technical estimate-tuning in a probabilistic combinatorics proof on a named 1977 conjecture. Like other single-author Zenodo claims, it needs expert checking before it counts.
What is disputed or not yet verified
| Verification | Unrefereed Zenodo preprint; rational-arithmetic checks with published code; not peer-reviewed or formalised |
|---|
Sources
3 sources from 2 sites. Numbers match the chips in the text.
3 sources: 3 primary
Primary
- Zenodo: The Borodin–Kostochka inequality from degree 1000 (L. Chen, 26 Oct 2026)zenodo.org, paper
- Zenodo: The Borodin–Kostochka conjecture for maximum degree at least 4583 (L. Chen)zenodo.org, paper
- arXiv 2603.16670: Liu, Sun, Wang, Zeng, On the Borodin–Kostochka conjecture for graphs with large maximum degreearxiv.org, paper
Changes
- New Zenodo version claims Δ ≥ 1000 (record 23653610), AI disclosure quoted
- Filed (Zenodo; PDF read with pdftotext)