Pach–Tardos conjecture

Pach and Tardos conjectured in 2005 that every acyclic matrix pattern $P$ has near-linear extremal function, specifically $\operatorname{Ex}(P,n)=O(n\log^{C_P}n)$.

Known results

• The conjecture had been established for all patterns of weight at most $5$ and all but two patterns of weight $6$.
• Pettie and Tardos, 2024, claimed sharp bounds $\operatorname{Ex}(P_t,n)=\Theta\!\left(n\left(\frac{\log n}{\log\log n}\right)^t\right)$ for alternating patterns.
• Their 2024 preprint claimed counterexamples $S_0,S_1$ with $\operatorname{Ex}(S_i,n)\ge n2^{\Omega(\sqrt{\log n})}$, refuting the conjecture.

September 17, 2026 claimed proof

On September 17, 2026, Lior Gishboliner and Xiangyu Li submitted Proof of the Pach-Tardos conjecture, claiming for every acyclic $P$ that $\operatorname{Ex}(n,P)\le n^{1+O_P(1/\log\log n)}$. This directly conflicts with the 2024 refutation claim and is supported only by an unrefereed preprint.

Current status (as of September 2026): A new preprint claims the conjecture is proved, while the earlier counterexample claim and the new proof have not been independently verified, so the exact mathematical status remains unresolved.