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

Abstract 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}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>P</mml:mi> <mml:mo>∈</mml:mo> <mml:msup> <mml:mrow> <mml:mo>{</mml:mo> <mml:mn>0</mml:mn> <mml:mo>,</mml:mo> <mml:mn>1</mml:mn> <mml:mo>}</mml:mo> </mml:mrow> <mml:mrow> <mml:mi>k</mml:mi> <mml:mo>×</mml:mo> <mml:mi>l</mml:mi> </mml:mrow> </mml:msup> </mml:mrow> </mml:math> is acyclic , meaning it is the bipartite incidence matrix of a forest, then $$\operatorname {Ex}(P,n) = O(n\log ^{C_P} n)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mo>Ex</mml:mo> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>P</mml:mi> <mml:mo>,</mml:mo> <mml:mi>n</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> <mml:mo>=</mml:mo> <mml:mi>O</mml:mi> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>n</mml:mi> <mml:msup> <mml:mo>log</mml:mo> <mml:msub> <mml:mi>C</mml:mi> <mml:mi>P</mml:mi> </mml:msub> </mml:msup> <mml:mi>n</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> </mml:math> , where $$\operatorname {Ex}(P,n)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mo>Ex</mml:mo> <mml:mo>(</mml:mo> <mml:mi>P</mml:mi> <mml:mo>,</mml:mo> <mml:mi>n</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> is the maximum number of 1s in a P -free $$n\times n$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>n</mml:mi> <mml:mo>×</mml:mo> <mml:mi>n</mml:mi> </mml:mrow> </mml:math> 0–1 matrix and $$C_P$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>C</mml:mi> <mml:mi>P</mml:mi> </mml:msub> </mml:math> 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})}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mo>Ex</mml:mo> <mml:mrow> <mml:mo>(</mml:mo> <mml:msub> <mml:mi>S</mml:mi> <mml:mn>0</mml:mn> </mml:msub> <mml:mo>,</mml:mo> <mml:mi>n</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> <mml:mo>,</mml:mo> <mml:mo>Ex</mml:mo> <mml:mrow> <mml:mo>(</mml:mo> <mml:msub> <mml:mi>S</mml:mi> <mml:mn>1</mml:mn> </mml:msub> <mml:mo>,</mml:mo> <mml:mi>n</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> <mml:mo>≥</mml:mo> <mml:mi>n</mml:mi> <mml:msup> <mml:mn>2</mml:mn> <mml:mrow> <mml:mi>Ω</mml:mi> <mml:mo>(</mml:mo> <mml:msqrt> <mml:mrow> <mml:mo>log</mml:mo> <mml:mi>n</mml:mi> </mml:mrow> </mml:msqrt> <mml:mo>)</mml:mo> </mml:mrow> </mml:msup> </mml:mrow> </mml:math> , where $$S_0,S_1$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mi>S</mml:mi> <mml:mn>0</mml:mn> </mml:msub> <mml:mo>,</mml:mo> <mml:msub> <mml:mi>S</mml:mi> <mml:mn>1</mml:mn> </mml:msub> </mml:mrow> </mml:math> are the outstanding weight-6 patterns. We also prove sharp bounds on the entire class of alternating patterns $$(P_t)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mo>(</mml:mo> <mml:msub> <mml:mi>P</mml:mi> <mml:mi>t</mml:mi> </mml:msub> <mml:mo>)</mml:mo> </mml:mrow>