Pettie, Seth and Tardos, Gábor (2025) A Refutation of the Pach-Tardos Conjecture for 0–1 Matrices. In: 36th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2025. Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (1). Society for Industrial and Applied Mathematics (SIAM), Philadelphia (PA), pp. 4462-4483. ISBN 9781611978322; 9798331312008
|
Text
1.9781611978322.1521.pdf - Published Version Download (862kB) | Preview |
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 (Formula presented).is acyclic, meaning it is the bipartite incidence matrix of a forest, then (Formula presented)., where Ex(Formula presented). is the maximum number of 1s in a P-free (Formula presented)matrix and 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(Formula presented).where S0,S1 are the outstanding weight-6 patterns.(Formula presented).We also prove sharp bounds on the entire class of alternating patterns (Formula presented)., specifically that for every (Formula presented). This is the first proof of an asymptotically sharp bound that is (Formula presented). Copyright © 2025.
| Item Type: | Book Section |
|---|---|
| Additional Information: | ACM Special Interest Group on Algorithms and Computation Theory (SIGACT); SIAM Activity Group on Discrete Mathematics Conference code: 205922 Export Date: 3 March 2025 CODEN: PAAAF Funding details: Engineering Research Centers, ERC Funding details: National Science Foundation, NSF, CCF-2221980 Funding details: Nemzeti Kutatási Fejlesztési és Innovációs Hivatal, NKFIH, K-132696, SNN-135643 Funding text 1: Supported by NSF Grant CCF-2221980. Supported by the National Research, Development and Innovation Office projects K-132696 and SNN-135643 and by the ERC Advanced Grants \\u201CERMiD\\u201D and \\u201CGeoScape.\\u201D |
| Uncontrolled Keywords: | MATRIX; Matrix algebra; Computational geometry; Trees (mathematics); Bipartite subgraphs; Sharp bounds; Graph parameters; Incidence matrices; forbidden pattern; 0-1 matrixes; Self-adjusting data structures; |
| Subjects: | Q Science / természettudomány > QA Mathematics / matematika |
| SWORD Depositor: | MTMT SWORD |
| Depositing User: | MTMT SWORD |
| Date Deposited: | 16 Jul 2025 05:29 |
| Last Modified: | 16 Jul 2025 05:29 |
| URI: | https://real.mtak.hu/id/eprint/221131 |
Actions (login required)
 |
Edit Item |
