---
id: "2026-10-20-borodin-kostochka-threshold-4583-gpt-6-astra"
url: "https://postcutoff.com/e/2026-10-20-borodin-kostochka-threshold-4583-gpt-6-astra/"
as_of: "2026-10-20T07:28:00+02:00"
date: "2026-10-20"
date_precision: day
category: science
importance: 3
confidence: medium
status: [Awaiting review]
verification: Preprint only
sources: 2
editor: human editor
human_review: null
version: null
---

As of: 2026-10-20 07:28 CEST.
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-20-borodin-kostochka-threshold-4583-gpt-6-astra/

# Borodin–Kostochka conjecture claimed for maximum degree ≥ 4583, with GPT-6 Astra assisting

Full title: Borodin–Kostochka conjecture claimed for maximum degree ≥ 4583 (down from 5.3 million), with GPT-6 Astra assisting

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}. The best published threshold was 5.3 × 10⁶ (Liu, Sun, Wang and Zeng, 2026). Its "Declaration of AI use" says OpenAI GPT-6 Astra assisted with the resampling estimates, moment-bound optimisation, local-lemma parameter choices and small-deficit constructions. Unrefereed; the conjecture stays open for 9 ≤ Δ < 4583.

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

## Your AI and this story

- GPT-6 Astra (training cutoff April 2026): 173 days after its cutoff
- Claude Opus 5.5 (training cutoff June 2026): 112 days after its cutoff
- Gemini 4 Argon (training cutoff March 2026): 203 days after its cutoff
- Grok 4.7 (training cutoff May 2026): 142 days after its cutoff

## Sources

1. [Zenodo: The Borodin–Kostochka conjecture for maximum degree at least 4583 (L. Chen)](https://zenodo.org/records/23487163) (zenodo.org, paper)
2. [arXiv 2603.16670: Liu, Sun, Wang, Zeng, On the Borodin–Kostochka conjecture for graphs with large maximum degree](https://arxiv.org/abs/2603.16670v3) (arxiv.org, paper)

## Changes

- 2026-10-20 (filed): Created (Zenodo; PDF read with pdftotext)

## Related

- 2026-10-19: [AI-assisted maths on Zenodo, 17–19 Oct 2026](https://postcutoff.com/e/2026-10-19-ai-assisted-results-zenodo-october-17-19/index.md)
- 2026-09-29: [List Total Colouring Conjecture (late 1990s) disproved](https://postcutoff.com/e/2026-09-29-list-total-colouring-conjecture-false-astra/index.md)