The Zarankiewicz problem on tripartite graphs
Abstract
Abstract In 1975, Bollobás, Erdős, and Szemerédi asked for the smallest such that an tripartite graph with minimum degree must contain , conjecturing that for . We prove that which confirms their conjecture and is best possible assuming the widely believed conjecture that the Zarankiewicz number satisfies . Our proof uses a density increment argument. We also construct an infinite family of extremal graphs that are pairwise far apart (requiring the change of edges to get between any two).
Fields of Study & Subjects
Limits and Structures in Graph Theory
Analytic Number Theory Research
Finite Group Theory Research
Publication details
- Journal / source
- Journal of the London Mathematical Society
- Volume
- 114
- Issue
- 1
- Publication date
- 1 July 2026
- Language
- EN