Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published July 2022 | Submitted
Journal Article Open

Some remarks on the Zarankiewicz problem


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.

Additional Information

© The Author(s), 2021. Published by Cambridge University Press on behalf of Cambridge Philosophical Society. Received 27 July 2020; revised 12 April 2021; accepted 14 April 2021. Published online by Cambridge University Press: 15 June 2021. I would like to thank Cosmin Pohoata for helpful discussions. I am also grateful to Dhruv Mubayi for drawing my attention to his work with Alon, Mellinger and Verstraëte [1].

Attached Files

Submitted - 2007.12816.pdf


Files (154.1 kB)
Name Size Download all
154.1 kB Preview Download

Additional details

August 20, 2023
October 20, 2023