Published July 2022
| Version Submitted
Journal Article
Open
Some remarks on the Zarankiewicz problem
Creators
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.
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
2007.12816.pdf
Files
(154.1 kB)
| Name | Size | Download all |
|---|---|---|
|
md5:9c9c324ed3de5c1c2207bce5c1ce46aa
|
154.1 kB | Preview Download |
Additional details
Identifiers
- Eprint ID
- 105368
- Resolver ID
- CaltechAUTHORS:20200914-085046091
Related works
- Describes
- https://arxiv.org/abs/2007.12816 (URL)
Dates
- Created
-
2020-09-14Created from EPrint's datestamp field
- Updated
-
2022-07-11Created from EPrint's last_modified field