Conlon, David (2022) Some remarks on the Zarankiewicz problem. Mathematical Proceedings of the Cambridge Philosophical Society, 173 (1). pp. 155-161. ISSN 0305-0041. doi:10.1017/S0305004121000475. https://resolver.caltech.edu/CaltechAUTHORS:20200914-085046091
![[img]](https://authors.library.caltech.edu/style/images/fileicons/application_pdf.png) |
PDF
- Submitted Version
See Usage Policy. 154kB |
Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20200914-085046091
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.
| Item Type: | Article | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Related URLs: |
| |||||||||
| ORCID: |
| |||||||||
| 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]. | |||||||||
| Issue or Number: | 1 | |||||||||
| Classification Code: | 2020 Mathematics Subject Classification: 05C35 (primary), 05D40 (secondary) | |||||||||
| DOI: | 10.1017/S0305004121000475 | |||||||||
| Record Number: | CaltechAUTHORS:20200914-085046091 | |||||||||
| Persistent URL: | https://resolver.caltech.edu/CaltechAUTHORS:20200914-085046091 | |||||||||
| Official Citation: | CONLON, D. (2022). Some remarks on the Zarankiewicz problem. Mathematical Proceedings of the Cambridge Philosophical Society, 173(1), 155-161. doi:10.1017/S0305004121000475 | |||||||||
| Usage Policy: | No commercial reproduction, distribution, display or performance rights in this work are provided. | |||||||||
| ID Code: | 105368 | |||||||||
| Collection: | CaltechAUTHORS | |||||||||
| Deposited By: | Tony Diaz | |||||||||
| Deposited On: | 14 Sep 2020 16:53 | |||||||||
| Last Modified: | 11 Jul 2022 22:31 |
Repository Staff Only: item control page
