CaltechAUTHORS
  A Caltech Library Service

Some remarks on the Zarankiewicz problem

Conlon, David (2020) Some remarks on the Zarankiewicz problem. . (Unpublished) https://resolver.caltech.edu/CaltechAUTHORS:20200914-085046091

[img] PDF - Submitted Version
See Usage Policy.

150Kb

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:Report or Paper (Discussion Paper)
Related URLs:
URLURL TypeDescription
http://arxiv.org/abs/2007.12816arXivDiscussion Paper
ORCID:
AuthorORCID
Conlon, David0000-0001-5899-1829
Additional Information: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].
Record Number:CaltechAUTHORS:20200914-085046091
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20200914-085046091
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:14 Sep 2020 16:53

Repository Staff Only: item control page