Projects per year
Abstract
For positive integers (Formula presented.), (Formula presented.), (Formula presented.) and (Formula presented.), the Zarankiewicz number (Formula presented.) is defined to be the maximum number of edges in a bipartite graph with parts of sizes (Formula presented.) and (Formula presented.) that has no complete bipartite subgraph containing (Formula presented.) vertices in the part of size (Formula presented.) and (Formula presented.) vertices in the part of size (Formula presented.). A simple argument shows that, for each (Formula presented.), (Formula presented.) when (Formula presented.). Here, for large (Formula presented.), we determine the exact value of (Formula presented.) in almost all of the remaining cases where (Formula presented.). We establish a new family of upper bounds on (Formula presented.) 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.
| Original language | English |
|---|---|
| Pages (from-to) | 81-109 |
| Number of pages | 29 |
| Journal | Journal of Graph Theory |
| Volume | 106 |
| Issue number | 1 |
| DOIs | |
| Publication status | Published - May 2024 |
Keywords
- linear hypergraph
- Zarankiewicz number
- Zarankiewicz problem
-
The Zarankiewicz problem through linear hypergraphs and designs
Horsley, D. (Primary Chief Investigator (PCI))
1/10/22 → 30/09/26
Project: Research
-
Edge decomposition of dense graphs
Horsley, D. (Primary Chief Investigator (PCI))
ARC - Australian Research Council
30/06/17 → 31/10/22
Project: Research
Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver