Extremal numbers of acyclic matrices

Abstract

For a zero-one matrix $P$, let $\mathrm{Ex}(n,P)$ denote the maximum number of ones in an $n\times n$ zero-one matrix avoiding $P$. We prove that $$\mathrm{Ex}(n,P)\le n^{1+O_P(1/\log \log n)}$$ for every acyclic $P$, settling the weak form of the Pach-Tardos conjecture.

arXiv commentRevised title and substantially simplified proof