ChatGPT Astra finds geometric triangle-free graphs with near-optimal chromatic number, the first improvement on Burling's 1965 box bound
On Oct 2, 2026 István Tomon (Umeå University) posted geometric constructions of triangle-free and high-girth graphs with rapidly growing chromatic number. The headline result is a triangle-free intersection graph of n boxes in R³ with chromatic number (log n)^(1−o(1)). He calls it the first improvement over Burling's double-logarithmic bound from 1965, and it nearly matches the O(log n) upper bound. The paper states: "The constructions presented in this paper were found by ChatGPT Astra after guidance from the author."
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.'
Science result
- Field
- mathematics / combinatorics / discrete geometry
- Problem
- Chromatic number of triangle-free geometric intersection graphs (boxes in R³; Burling 1965) and related girth problems (open since 1965)
- Result
- Triangle-free box intersection graphs with χ = (log n)^(1−o(1)), plus girth-g unit-distance, line and circle-tangency constructions.
- AI system
- GPT-6 Astra
- Human role
- AI-found constructions: the author guided ChatGPT Astra (asking for parametric families), then wrote the exposition and analysis
- Verification
- Unrefereed preprint
- Status
- pending
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.
Changelog
- 2026-10-05: created (06:30 run; arXiv paper missed by the sweep's date window, AI declaration read in the PDF)
Related events
- Summer 2026 flood: dozens of named conjectures settled on arXiv with disclosed AI help (July–September catalogue) ★★★★
- Erdős–Hajnal high-girth problem (Erdős #108) disproved with ChatGPT/Codex help and a Lean proof, via the Conjectures.io bounty; experts sharpen it with GPT-6 Astra ★★★★
Sources (1)
id: 2026-10-02-tomon-triangle-free-box-graphs-astra · updated 2026-10-05 · open in the interactive timeline