In 1975, Bollob\'{ a}s, Erd\H{ o}s, and Szemer\'{ e}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/2})$ for $t = 2$. We prove that $\tau = \mathcal{ O}(n^{ 1 - 1/t})$ which confirms their conjecture and is best possible assuming the widely believed conjecture that $\operatorname{ ex}(n, K_{ t, t}) = \Theta(n^{ 2 - 1/t})$. Our proof uses a density increment argument. We also construct an infinite family of extremal graphs.
Categories: math.CO