Complete tripartite subgraphs of balanced tripartite graphs with large minimum degree

Abstract

In 1975 Bollobás, Erdős, and Szemerédi asked what minimum degree guarantees an octahedral subgraph $K_3(2)$ in any tripartite graph $G$ with $n$ vertices in each vertex class. We show that $\hat{I}´(G)\ge n+2n^{\frac{5}{6}}$ suffices thus improving the bound $n+(1+o(1))n^{\frac{11}{12}}$ of Bhalkikar and Zhao obtained by following their approach. Bollobás, Erdős, and Szemerédi conjectured that $n+c{n}^{\frac{1}{2}}$ suffices and there are many $K_3(2)$-free tripartite graphs $G$ with $\hat{I}´(G)\ge n+c{n}^{\frac{1}{2}}$. We confirm this conjecture under the additional assumption that every vertex in $G$ is adjacent to at least $(1/5+\epsilon )n$ vertices in any other vertex class.

We modified Section 4, replaced Construction 4.1 with a new example