Some remarks on the Zarankiewicz problem

Abstract

The Zarankiewicz problem asks for an estimate on $z(m,n;s,t)$, the largest number of $1$'s in an $m\times n$ matrix with all entries $0$ or $1$ containing no $s\times t$ submatrix consisting entirely of $1$'s. We show that a classical upper bound for $z(m,n;s,t)$ due to Kővári, Sós and Turán is tight up to the constant for a broad range of parameters. The proof relies on a new quantitative variant of the random algebraic method.

6 pages