The weak Pach-Tardos conjecture for acyclic matrix patterns

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.

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