---
id: "2026-11-05-quasiplanar-graphs-linear-edges-chatgpt-6-pach-tardos-zeng"
url: "https://postcutoff.com/e/2026-11-05-quasiplanar-graphs-linear-edges-chatgpt-6-pach-tardos-zeng/"
as_of: "2026-11-09T21:13:00+01:00"
date: "2026-11-05"
date_precision: day
category: science
importance: 4
confidence: medium
status: [Awaiting review]
verification: Expert-checked
sources: 3
editor: human editor
human_review: null
version: "2026-11-08"
---

As of: 2026-11-09 21:13 CET.
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-11-05-quasiplanar-graphs-linear-edges-chatgpt-6-pach-tardos-zeng/

# Quasiplanar graph conjecture proved by ChatGPT-6 (Pach, Tardos, Zeng)

Full title: Pach–Shahrokhi–Szegedy quasiplanar conjecture: 'ChatGPT produced a proof', say Pach, Tardos and Zeng, who post a simplified version; k-quasiplanar graphs have O_k(n) edges

arXiv 2611.07314 (János Pach, Gábor Tardos, Ji Zeng; 5 Nov 2026) states that ChatGPT-6 produced a proof of the conjecture of Pach, Shahrokhi and Szegedy that k-quasiplanar topological graphs on n vertices have O_k(n) edges, and presents a simplified, purely combinatorial version. Before this the bound was known only for k ≤ 4. A separate preprint by Ankan Sadhu (arXiv 2611.01509, 1 Nov), which says AI only helped with literature and LaTeX, claims a proof with a similar strategy.

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

## Your AI and this story

- GPT-6 Astra (training cutoff April 2026): 189 days after its cutoff
- Claude Opus 5.5 (training cutoff June 2026): 128 days after its cutoff
- Gemini 4 Argon (training cutoff March 2026): 219 days after its cutoff
- Grok 4.7 (training cutoff May 2026): 158 days after its cutoff

## Sources

1. [Pach, Tardos, Zeng: On the number of edges in quasiplanar graphs (arXiv 2611.07314)](https://arxiv.org/abs/2611.07314) (arxiv.org, paper)
2. [Sadhu: Every k-Quasi-Planar Graph Has Linearly Many Edges (arXiv 2611.01509)](https://arxiv.org/abs/2611.01509) (arxiv.org, paper)
3. [Fox, Pach, Suk: Quasiplanar graphs, string graphs, and the Erdős–Gallai problem (arXiv 2112.02378)](https://arxiv.org/abs/2112.02378) (arxiv.org, paper)

## Changes

- 2026-11-08 (filed): Created (science agent; both PDFs read)