The Pach-Tardos conjecture is an extremal assertion about 0-1 matrices. For a fixed 0-1 matrix 
, let 
be the maximum number of 1s in an 
0-1 matrix that contains
no copy of 
,
where a copy may be obtained from a submatrix by changing
some of its 1s to 0s. The pattern 
is acyclic if its Levi graph
(incidence graph) is a forest.
The Pach-Tardos conjecture (Pach and Tardos 2006) predicted a polylogarithmic factor above linear growth for every acyclic 
. Pettie and Tardos (2025) refuted that form of the conjecture.
Its weak form asserts
 |
Gishboliner and Li (2026) proved the weak form, more precisely obtaining 
.
Gishboliner and Li (2026) credit ChatGPT-6 Astra with finding the proof under substantial guidance from the authors, who checked and rewrote it. As of Sep. 22, 2026, independent specialist review had not been reported.
