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\H{ o}v\'ari, S\'os and Tur\'an 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.
Categories: math.CO