Weak Pach–Tardos bounds for acyclic matrix patterns
Follow the latest progress by email.
For a fixed acyclic 0–1 matrix pattern P, how many ones can an n×n matrix contain while avoiding P? The weak Pach–Tardos target is Ex(n,P)=n^(1+o(1)).
Why it matters and what counts as progress
Why it matters: The weak almost-linear statement survives the failure of the stronger n·polylog n prediction.
What counts as progress: A bound n^(1+O_P(1/log log n)) or better for every fixed acyclic pattern, or a super-near-linear counterexample.
How the problem developed
- 2025 · Counterexample [1]
Seth Pettie and Gábor Tardos Refuted the strong Pach–Tardos prediction of a linear bound times a polylogarithmic factor for all acyclic patterns.
- 17 Sept 2026 · Reported claim [2]
Lior Gishboliner and Xiangyu Li Proved the weak form for every acyclic 0–1 pattern, with Ex(n,P) ≤ n^(1+O_P(1/log log n)); their later version records substantial proof revisions.
AI contribution
Proof of the Pach-Tardos conjecture
For each fixed acyclic 0–1 matrix pattern P, Gishboliner and Li prove Ex(n,P)≤n^(1+O_P(1/log log n)), establishing the weak n^(1+o(1)) Pach–Tardos statement.
Sources
Website timeline
Publication dates and editorial changes.