Quasiplanar graph conjecture proved by ChatGPT-6 (Pach, Tardos, Zeng)
Awaiting review
Importance: major (4 of 5)The takeaway
János Pach, one of the conjecture’s authors, with Gábor Tardos and Ji Zeng, writes that ChatGPT-6 proved that graphs drawn with no k pairwise crossing edges have linearly many edges, a conjecture known only for k ≤ 4. Their note gives a self-contained combinatorial version; an independent human preprint by Ankan Sadhu (1 Nov) claims a similar proof.
Status
- Claim
Awaiting review
- Our reporting
- Medium confidence
- Verification
- Expert-checked
- Importance
- Major (4 of 5)
- Last verified
- 8 November 2026
Your AI and this story
- GPT-6 Astra189 days after its cutoff
- Claude Opus 5.5128 days after its cutoff
- Gemini 4 Argon219 days after its cutoff
- Grok 4.7158 days after its cutoff
None of these four assistants can know about it. The closest, Claude Opus 5.5, stops 128 days before it.
Key facts
- Statement: a k-quasiplanar graph (drawn in the plane with no k pairwise crossing edges) on n vertices has O_k(n) edges; the authors’ constants give at most 2^{(2+o(1)) k log₂ k} n edges
- Before: known only for k ≤ 4 (Agarwal–Aronov–Pach–Pollack–Sharir, Ackerman–Tardos, Ackerman); for fixed k ≥ 5 the best bound was Fox–Pach–Suk’s O_k(n (log n)^{2⌈log₂ k⌉−4})
- AI disclosure (abstract): ‘ChatGPT produced a proof of this conjecture. Here, we present a simplified, self-contained version of that proof.’ Body: ‘The argument produced by ChatGPT relies on a paper by Beeker and Lazarovich … we present a self-contained and purely combinatorial version’; acknowledgements: ‘an effort to interpret and simplify a proof generated by ChatGPT-6’
- Independent claim: Ankan Sadhu, ‘Every k-Quasi-Planar Graph Has Linearly Many Edges’ (arXiv 2611.01509, 1 Nov); its declaration says GPT-5.6 Sol only helped with literature search and converting the author’s handwritten proof to LaTeX. Pach–Tardos–Zeng note it uses ‘a strategy very similar to the one initially provided to us by ChatGPT’
- Verification status: preprints; the human-simplified version is by leading experts in the area (Pach is a co-author of the conjecture); not refereed
What happened
On 5 Nov 2026 János Pach, Gábor Tardos and Ji Zeng posted a short paper. It opens by saying that ChatGPT produced a proof of the conjecture of Pach, Shahrokhi and Szegedy that graphs drawn with no k pairwise crossing edges have linearly many edges. The model’s argument used a topological paper by Beeker and Lazarovich. The three authors rewrote it as a self-contained combinatorial proof. Four days earlier, Ankan Sadhu had posted a proof he describes as his own, with a similar strategy.
Why it matters
This is a well-known problem in geometric graph theory, and the experts most associated with it confirm the AI-originated argument in their own write-up. Two near-simultaneous proofs of the same conjecture also show how hard it is becoming to assign priority.
What is disputed or not yet verified
| Verification | Expert-checked preprint (by the conjecture’s co-author); not refereed |
|---|
Sources
3 sources from 1 site. Numbers match the chips in the text.
3 sources: 3 primary
Primary
- Pach, Tardos, Zeng: On the number of edges in quasiplanar graphs (arXiv 2611.07314)arxiv.org, paper
- Sadhu: Every k-Quasi-Planar Graph Has Linearly Many Edges (arXiv 2611.01509)arxiv.org, paper
- Fox, Pach, Suk: Quasiplanar graphs, string graphs, and the Erdős–Gallai problem (arXiv 2112.02378)arxiv.org, paper
Changes
- Filed (science agent; both PDFs read)