2024/07/02 by Seth Pettie, Gábor Tardos, Pettie, Seth +1
Computer Science · Physics and Astronomy · Engineering · #Matrix Theory and Algorithms #Advanced Mathematical Theories and Applications #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2407.02638
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(nlogCP 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(S0,n),Ex(S1,n) ≥ n2Ω(√(log n)), where S0,S1 are the outstanding weight-6 patterns. We also prove sharp bounds on the entire class of alternating patterns (Pt), specifically that for every t≥ 2, Ex(Pt,n)=Θ(n(log n/loglog n)t). This is the first proof of an asymptotically sharp bound that is ω(nlog n).