The Zarankiewicz problem on tripartite graphs

Abstract

In 1975, Bollobás, Erdős, and Szemerédi asked for the smallest $\ddot{I}„$ such that an $n\times n\times n$ tripartite graph with minimum degree $n+\ddot{I}„$ must contain $K_{t,t,t}$, conjecturing that $\ddot{I}„=\mathcal{O}(n^{1/2})$ for $t=2$. We prove that $\ddot{I}„=\mathcal{O}(n^{1-1/t})$ which confirms their conjecture and is best possible assuming the widely believed conjecture that the Zarankiewicz number satisfies $z(n;t)=\hat{I}˜(n^{2-1/t})$. 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 $\hat{I}\text{c◯}(n^2)$ edges to get between any two).

24 pages, final version