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\in \{0,1\}^{k\times l}\) is acyclic, meaning it is the bipartite incidence matrix of a forest, then \(\operatorname {Ex}(P,n) = O(n\log ^{C_P} n)\) , where \(\operatorname {Ex}(P,n)\) is the maximum number of 1s in a P-free \(n\times n\) 0–1 matrix and \(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 \(\operatorname {Ex}(S_0,n),\operatorname {Ex}(S_1,n) \ge n2^{\Omega (\sqrt{\log n})}\) , where \(S_0,S_1\) are the outstanding weight-6 patterns. We also prove sharp bounds on the entire class of alternating patterns \((P_t)\) , specifically that for every \(t\ge 2\) , \(\operatorname {Ex}(P_t,n)=\Theta (n(\log n/\log \log n)^t)\) . This is the first proof of an asymptotically sharp bound that is \(\omega (n\log n)\) .
