Combinatorica Вычислительная математика

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

Seth Pettie, Gábor Tardos
Springer Nature · 2025-11-07 · DOI 10.1007/s00493-025-00187-7

Аннотация

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

Читать у издателя →