Hostname: page-component-586b7cd67f-rcrh6 Total loading time: 0 Render date: 2024-11-23T14:32:42.626Z Has data issue: false hasContentIssue false
  • English
  • Français

Some remarks on the Zarankiewicz problem

Part of: Graph theory Extremal combinatorics

Published online by Cambridge University Press:  15 June 2021

DAVID CONLON
DAVID CONLON*
Affiliation:
Department of Mathematics, California Institute of Technology, 1200 E. California Boulevard, Pasadena, CA91125, U.S.A. e-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

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.

MSC classification

Primary: 05C35: Extremal problems
Secondary: 05D40: Probabilistic methods
Type
Research Article
Information
Mathematical Proceedings of the Cambridge Philosophical Society , Volume 173 , Issue 1 , July 2022 , pp. 155 - 161
Copyright
© The Author(s), 2021. Published by Cambridge University Press on behalf of Cambridge Philosophical Society

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Alon, N., Mellinger, K. E., Mubayi, D. and Verstraëte, J.. The de Bruijn–Erdős theorem for hypergraphs. Des. Codes Cryptogr. 65 (2012), 233–245.CrossRefGoogle Scholar
Alon, N., Rónyai, L. and Szabó, T.. Norm-graphs: variations and applications. J. Combin. Theory Ser. B 76 (1999), 280–290.CrossRefGoogle Scholar
Blagojević, P. V. M., Bukh, B. and Karasev, R.. Turán numbers for K s, t-free graphs: topological obstructions and algebraic constructions. Israel J. Math. 197 (2013), 199–214.CrossRefGoogle Scholar
Brown, W. G.. On graphs that do not contain a Thomsen graph. Canad. Math. Bull. 9 (1966), 281–285.CrossRefGoogle Scholar
Bukh, B.. Random algebraic construction of extremal graphs. Bull. London. Math. Soc. 47 (2015), 939–945.Google Scholar
Bukh, B. and Conlon, D.. Rational exponents in extremal graph theory. J. Eur. Math. Soc. 20 (2018), 1747–1757.CrossRefGoogle Scholar
Bukh, B. and Goaoc, X.. Shatter functions with polynomial growth rates. SIAM J. Discrete Math. 33 (2019), 784–794.CrossRefGoogle Scholar
Conlon, D.. Graphs with few paths of prescribed length between any two vertices. Bull. Lond. Math. Soc. 51 (2019), 1015–1021.CrossRefGoogle Scholar
Conlon, D., Janzer, O. and Lee, J.. More on the extremal number of subdivisions, to appear in Combinatorica.Google Scholar
Conlon, D. and Tyomkyn, M.. Repeated patterns in proper colourings, preprint available at arXiv:2002.00921.Google Scholar
Erdős, P.. On sequences of integers no one of which divides the product of two others and on some related problems. Mitt. Forsch.-Inst. Math. Mech. Univ. Tomsk 2 (1938), 74–82.Google Scholar
Erdős, P.. On the combinatorial problems which I would most like to see solved. Combinatorica 1 (1981), 25–42.CrossRefGoogle Scholar
Fulton, W.. Introduction to intersection theory in algebraic geometry, CBMS Regional Conference Series in Mathematics, 54, (American Mathematical Society, Providence, RI, 1984).CrossRefGoogle Scholar
Janzer, O.. The extremal number of the subdivisions of the complete bipartite graph. SIAM J. Discrete Math. 34 (2020), 241–250.CrossRefGoogle Scholar
Jiang, T., Jiang, Z. and Ma, J.. Negligible obstructions and Turán exponents, preprint available at arXiv:2007.02975.Google Scholar
Jiang, T., Ma, J. and Yepremyan, L.. On Turán exponents of bipartite graphs, preprint available at arXiv:1806.02838.Google Scholar
Jiang, T. and Qiu, Y.. Many Turán exponents via subdivisions, preprint available at arXiv:1908.02385.Google Scholar
Kang, D. Y., Kim, J. and Liu, H.. On the rational Turán exponents conjecture. J. Combin. Theory Ser. B 148 (2021), 149–172.CrossRefGoogle Scholar
Kollár, J., Rónyai, L. and Szabó, T.. Norm-graphs and bipartite Turán numbers. Combinatorica 16 (1996), 399–406.CrossRefGoogle Scholar
Kővári, T., Sós, V. T. and Turán, P.. On a problem of K. Zarankiewicz. Colloq. Math. 3 (1954), 50–57.CrossRefGoogle Scholar
Matoušek, J.. On discrepancy bounds via dual shatter function. Mathematika 44 (1997), 42–49.CrossRefGoogle Scholar
Zarankiewicz, K.. Problem 101. Colloq. Math. 2 (1951), 301.Google Scholar