ChatGPT Astra finds geometric triangle-free graphs with near-optimal chromatic number, the first improvement on Burling’s 1965 box bound
Event confirmedAwaiting review
The takeaway
On Oct 2, 2026 István Tomon (Umeå University) posted geometric constructions of triangle-free and high-girth graphs with rapidly growing chromatic number.
Status
- Claim
Event confirmedAwaiting review
- Our reporting
- High confidence
- Verification
- Preprint only
- Importance
- 3 of 5
- Last verified
- 5 October 2026
Your AI and this story
- GPT-6.2 Astra124 days after its cutoff
- Claude Opus 5.594 days after its cutoff
- Gemini 4 Hydrogen185 days after its cutoff
- Grok 4.7124 days after its cutoff
None of these four assistants can know about it. The closest, Claude Opus 5.5, stops 94 days before it.
Key facts
- arXiv 2610.03517 (math.CO), ‘Geometric triangle-free graphs of large chromatic number’, Oct 2, 2026
- Boxes in R³: triangle-free intersection graph with independence number n(log n)^(−1+o(1)), so χ = (log n)^(1−o(1)); answers a question of Walczak
- Unit-distance graphs: if R^d has a unit-distance graph with chromatic number r, it also has an induced one with girth ≥ g and the same chromatic number
- Lines in R³ and circle tangency graphs with girth ≥ g and χ = Ω_g((log n)^(1−o(1))), improving Davies and Davies–Keller–Kleist–Smorodinsky–Walczak and giving an alternative solution of Ringel’s circle problem; ordered graphs motivated by the Gyárfás–Sumner conjecture
- AI declaration: ‘The constructions presented in this paper were found by ChatGPT Astra after guidance from the author.’ And: ‘We instructed ChatGPT Astra to look specifically for parametric families, which quickly led to the main ideas presented in this paper.’
What happened
Burling’s 1965 construction gave triangle-free box intersection graphs whose chromatic number grows only like log log n. Tomon’s preprint reaches (log n)^(1−o(1)), close to the known O(log n) ceiling, and adds several related girth results. He credits all the constructions to ChatGPT Astra working under his guidance. In his words, “While this construction might seem like it came out of nowhere … we try to illuminate how it uses ideas from known constructions … (So we can also claim some credit.)”
Why it matters
This is an exponential improvement on a 60-year-old bound in geometric graph colouring, and it is another case where the model supplied the constructions rather than routine checks. It is a preprint with no reactions found as of Oct 5.
What is disputed or not yet verified
| Verification | Unrefereed preprint |
|---|
Sources
1 source from 1 site. Numbers match the chips in the text.
1 source: 1 primary
Primary
Changes
- Filed (AI declaration read in the PDF)