Exact values for some unbalanced Zarankiewicz numbers

DOI10.1002/JGT.23068MaRDI QIDQ6201027zbMATH OpenOpenAlexFDO

Authors Guangzhou Chen, Daniel Horsley, Adam Mammoliti

Publication date 25 March 2024

Published in Journal of Graph Theory (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

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

zbMATH Keywords

linear hypergraphZarankiewicz numberZarankiewicz problem

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Extremal problems in graph theory (05C35) Density (toughness, etc.) (05C42) Hypergraphs (05C65)

Abstract: For positive integers $s$, $t$, $m$ and $n$, the Zarankiewicz number $Z_{s,t}(m,n)$ is defined to be the maximum number of edges in a bipartite graph with parts of sizes $m$ and $n$ that has no complete biparitite subgraph containing $s$ vertices in the part of size $m$ and $t$ vertices in the part of size $n$. A simple argument shows that, for each $tgeq2$, $$ when $$. Here, for large $m$, we determine the exact value of $Z_{2,t}(m,n)$ in almost all of the remaining cases where $n=Theta(t{m}^2)$. We establish a new family of upper bounds on $Z_{2,t}(m,n)$ which complement a family already obtained by Roman. We then prove that the floor of the best of these bounds is almost always achieved. We also show that there are cases in which this floor cannot be achieved and others in which determining whether it is achieved is likely a very hard problem. Our results are proved by viewing the problem through the lens of linear hypergraphs and our constructions make use of existing results on edge decompositions of dense graphs.

Recommendations

• New results on the Zarankiewicz problem
• Maximum number of edges of a bipartite graph without complete bipartite subgraphs
• Bipartite Ramsey numbers and Zarankiewicz numbers
• Extremal <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" altimg="si1.gif" overflow="scroll"><mml:msub><mml:mi>K</mml:mi><mml:mrow><mml:mo stretchy="false">(</mml:mo><mml:mi>s</mml:mi><mml:mo>,</mml:mo><mml:mi>t</mml:mi><mml:mo stretchy="false">)<
• Some imbalanced hypergraph Zarankiewicz numbers

Cites work

• A new result on the problem of Zarankiewicz
• A problem of Zarankiewicz
• Binding numbers and f-factors of graphs
• Bipartite Ramsey numbers and Zarankiewicz numbers
• scientific article; zbMATH DE number 3140515 (Why is no real title available?)
• scientific article; zbMATH DE number 3292554 (Why is no real title available?)
• scientific article; zbMATH DE number 3296261 (Why is no real title available?)
• List decomposition of graphs.
• Norm-graphs: Variations and applications
• On a problem of K. Zarankiewicz
• On the decomposition threshold of a given graph
• Some remarks on the Zarankiewicz problem
• Teilweise Lösung eines verallgemeinerten Problems von K. Zarankiewicz
• The de Bruijn-Erdős theorem for hypergraphs
• The Zarankiewicz problem, cages, and geometries
• Über ein Problem von K. Zarankiewicz

Cited in

(4)

• Zarankiewicz numbers near the triple system threshold
• Some imbalanced hypergraph Zarankiewicz numbers
• Improved upper bounds on Zarankiewicz numbers
• Super-simple balanced incomplete block designs with block size 5 and index 8

This page was built for publication: Exact values for some unbalanced Zarankiewicz numbers

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