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\^k l is the bipartite incidence matrix of an acyclic graph (forest), then Ex (P, n) = O (n^CP 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^ (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 (n/ n) ᵗ). This is the first proof of an asymptotically sharp bound that is (n n).