Hostname: page-component-7b7567c8c-tnkh4 Total loading time: 0 Render date: 2026-11-17T17:22:58.389Z Has data issue: false hasContentIssue false

Some remarks on the Zarankiewicz problem

Published online by Cambridge University Press:  15 June 2021

DAVID CONLON*
Affiliation:
Department of Mathematics, California Institute of Technology, 1200 E. California Boulevard, Pasadena, CA 91125, U.S.A. e-mail: dconlon@caltech.edu
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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.

MSC classification

Information

Type
Research Article
Copyright
© The Author(s), 2021. Published by Cambridge University Press on behalf of Cambridge Philosophical Society