PreprintarXiv licencearXiv
Extremal numbers of acyclic matrices
Abstract
For a zero-one matrix P, let Ex(n,P) denote the maximum number of ones in an n× n zero-one matrix avoiding P. We prove that Ex(n,P) ≤ n1+OP(1/loglog n) for every acyclic P, settling the weak form of the Pach-Tardos conjecture.
Related
- Extremal Graphs with Prescribed Parameters for the Spectral Radius of Weighted Adjacency Matrices with Property P∗
- Exact Values, Extremal Classifications, and Sum-of-Squares Reductions for Second-Order Zarankiewicz Numbers
- Matrix representations and arithmetic properties of jacobsthal numbers via binary 3x3 matrices
- On the Regularity and Clean Properties of Matrices over Dual Numbers
- Acyclic and totally acyclic objects in the Q-shaped derived category
BibTeX
@misc{gishboliner2026extremal,
title = {{Extremal numbers of acyclic matrices}},
author = {Lior Gishboliner and Xiangyu Li},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2609.20726},
eprint = {2609.20726},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.20726},
}
RIS
TY - UNPB
TI - Extremal numbers of acyclic matrices
AU - Lior Gishboliner
AU - Xiangyu Li
PY - 2026
DA - 2026/10/20
PB - arXiv
DO - 10.48550/arxiv.2609.20726
UR - https://arxiv.org/abs/2609.20726
AB - For a zero-one matrix P, let Ex(n,P) denote the maximum number of ones in an n× n zero-one matrix avoiding P. We prove that Ex(n,P) ≤ n^1+O_P(1/loglog n) for every acyclic P, settling the weak form of the Pach-Tardos conjecture.
ER -