The Zarankiewicz problem on tripartite graphs

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