CaltechAUTHORS
  A Caltech Library Service

Some remarks on the Zarankiewicz problem

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] 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:
URLURL TypeDescription
https://doi.org/10.1017/S0305004121000475DOIArticle
https://arxiv.org/abs/2007.12816arXivDiscussion Paper
ORCID:
AuthorORCID
Conlon, David0000-0001-5899-1829
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