The weak Pach-Tardos conjecture for acyclic matrix patterns

For a 0/1 pattern $P$ , let $\mathrm{Ex}(n,P)$ be the largest number of 1-entries in an $n \times n$ 0/1 matrix containing no copy of $P$ ; $P$ is acyclic when its bipartite incidence graph is a forest. Pach and Tardos conjectured in 2005 that $\mathrm{Ex}(n,P) \le n\,\mathrm{polylog}(n)$ for every acyclic $P$ . Pettie and Tardos refuted that in 2024, exhibiting acyclic patterns with $\mathrm{Ex}(n,P) \ge n\,2^{\Omega(\sqrt{\log n})}$ . The weaker form survives and is, in the authors' words, arguably one of the main open problems in the area: is $\mathrm{Ex}(n,P) \le n^{1+o(1)}$ for every acyclic $P$ ?

Result: Proved(see note)
Status: Resolved
AI contribution: AI co-developed
Method: Argument
Field: Extremal combinatorics; forbidden 0-1 matrices
Posed by: János Pach and Gábor Tardos (2005); the weak form is what survives Pettie and Tardos's 2024 refutation of the original
Year posed: 2005
Years open: 21y
Solved: 2026-09-17
Model: ChatGPT-6 Astra
Vendor: OpenAI
Collaborators: Lior Gishboliner, Xiangyu Li
Verification: Unreviewed
Publication: Preprint
Significance: 35 / 100
Disclosed cost: —
Wikipedia: No dedicated article

What was actually shown

Proved, in the weak form: for every acyclic pattern $P$ , $\mathrm{Ex}(n,P) \le n^{1+O_P(1/\log\log n)}$ , hence $n^{1+o(1)}$ . Stated as Theorem 1 in the language of ordered bipartite graphs: for all $s,t \ge 1$ and $\varepsilon>0$ there is $n_0$ such that every $n \times n$ ordered bipartite graph with $n \ge n_0$ and at least $n^{1+\varepsilon}$ edges contains a copy of every $s \times t$ ordered bipartite tree. The paper does NOT restore the original polylog conjecture, which stays refuted.

What the AI did

The paper's declaration of AI use, in full: "The proof was found by ChatGPT-6 Astra, with substantial input and guidance from the authors. The authors then rewrote the proof and take full responsibility for its correctness."

Verification

Checked here on 22 September 2026 against arXiv:2609.20726. The introduction was read and states the distinction this entry turns on: Pach and Tardos conjectured the polylog bound, Pettie and Tardos refuted it, and what is proved here is the weaker $n^{1+o(1)}$ form, restated as Theorem 1 for ordered bipartite trees and Corollary 2 as $\mathrm{Ex}(n,P) \le n^{1+O_P(1/\log\log n)}$ . The AI declaration is quoted verbatim. The mathematics was not checked here; five days old, no referee.

Claim issue

The title says "Proof of the Pach-Tardos conjecture" without qualification, but the conjecture in its published 2005 form was disproved by Pettie and Tardos in 2024. What is proved is the weaker $n^{1+o(1)}$ statement. The paper's own introduction is explicit about this; the title alone is not.

Sources

PaperProof of the Pach-Tardos conjecture, arXiv:2609.20726 (17 September 2026)Pettie and Tardos, the 2024 refutation of the original form