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

The theory of forbidden 0–1 matrices generalizes Turán-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 problem in this area is to resolve the Pach-Tardos conjecture from 2005, which states that if a forbidden pattern P∈ \0,1× l P ∈ { 0 , 1 } k × l is acyclic , meaning it is the bipartite incidence matrix of a forest, then Ex(P,n) = O(nlog CP n) Ex ( P , n ) = O ( n log C P n ) , where Ex(P,n) Ex ( P , n ) is the maximum number of 1s in a P -free n× n n × n 0–1 matrix and CP C P 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) Ex ( S 0 , n ) , Ex ( S 1 , n ) ≥ n 2 Ω ( log n ) , where S₀,S₁ S 0 , S 1 are the outstanding weight-6 patterns. We also prove sharp bounds on the entire class of alternating patterns (Pₜ) ( P t )