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×n matrix with all entries 0 or 1 containing no s×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.