Some remarks on the Zarankiewicz problem

DOI10.1017/S0305004121000475MaRDI QIDQ5081317zbMATH OpenOpenAlexFDO

Authors David Conlon

Publication date 14 June 2022

Published in Mathematical Proceedings of the Cambridge Philosophical Society (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2007.12816

zbMATH Keywords

maximum number of edges in a bipartite graphrandom algebraic method

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Extremal problems in graph theory (05C35) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Abstract: The Zarankiewicz problem asks for an estimate on $z(m,n;s,t)$, the largest number of $1$'s in an $mimesn$ matrix with all entries $0$ or $1$ containing no $simest$ submatrix consisting entirely of $1$'s. We show that a classical upper bound for $z(m,n;s,t)$ due to KH{o}v'ari, S'os and Tur'an 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.

Recommendations

• A contribution to the Zarankiewicz problem
• scientific article; zbMATH DE number 4198026
• On the half-half case of the Zarankiewicz problem
• scientific article; zbMATH DE number 1795865
• New results on the Zarankiewicz problem

Cites work

• Graphs with few paths of prescribed length between any two vertices
• scientific article; zbMATH DE number 3031694 (Why is no real title available?)
• More on the extremal number of subdivisions
• Norm-graphs and bipartite Turán numbers
• Norm-graphs: Variations and applications
• On a problem of K. Zarankiewicz
• On discrepancy bounds via dual shatter function
• On Graphs that do not Contain a Thomsen Graph
• On the combinatorial problems which I would most like to see solved
• On the rational Turán exponents conjecture
• Random algebraic construction of extremal graphs
• Rational exponents in extremal graph theory
• Shatter functions with polynomial growth rates
• The de Bruijn-Erdős theorem for hypergraphs
• The extremal number of the subdivisions of the complete bipartite graph
• Turán numbers for \(K_{s,t}\)-free graphs: topological obstructions and algebraic constructions

Cited in

(18)

• Bounds on certain multiplications of affine combinations
• On the half-half case of the Zarankiewicz problem
• scientific article; zbMATH DE number 5697231 (Why is no real title available?)
• scientific article; zbMATH DE number 1795865 (Why is no real title available?)
• scientific article; zbMATH DE number 4198026 (Why is no real title available?)
• scientific article; zbMATH DE number 3267421 (Why is no real title available?)
• scientific article; zbMATH DE number 3311770 (Why is no real title available?)
• Contributions to the problem of Zrankiewicz
• Exact values for some unbalanced Zarankiewicz numbers
• Continuous Tur\'an numbers
• Zarankiewicz numbers near the triple system threshold
• Extremal graphs without exponentially small bicliques
• Ramsey numbers and the Zarankiewicz problem
• Improved upper bounds on Zarankiewicz numbers
• A stability theorem for multi-partite graphs
• Applications of random algebraic constructions to hardness of approximation
• Compact representation of semilinear and terrain-like graphs
• A contribution to the Zarankiewicz problem

This page was built for publication: Some remarks on the Zarankiewicz problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5081317)