A Refutation of the Pach-Tardos Conjecture for 0-1 Matrices

The theory of forbidden 0-1 matrices generalizes Turan-style (bipartite) subgraph avoidance, Davenport-Schinzel theory, and Zarankiewicz-type problems, and has been influential in many areas, such as discrete and computational geometry, the analysis of self-adjusting data structures, and the development of the graph parameter twin width. The foremost open problems in this area is to resolve the Pach-Tardos conjecture from 2005, which states that if a forbidden pattern P∈\0,1× l is the bipartite incidence matrix of an acyclic graph (forest), then Ex(P,n) = O(nlogCP n), where CP is a constant depending only on P. This conjecture has been confirmed on many small patterns, specifically all P with weight at most 5, and all but two with weight 6. The main result of this paper is a clean refutation of the Pach-Tardos conjecture. Specifically, we prove that Ex(S₀,n),Ex(S₁,n) ≥ n2Ω(√log n), where S₀,S₁ are the outstanding weight-6 patterns. We also prove sharp bounds on the entire class of alternating patterns (Pₜ), specifically that for every t≥ 2, Ex(Pₜ,n)=Θ(n(log n/loglog n)ᵗ). This is the first proof of an asymptotically sharp bound that is ω(nlog n).