An exact Turán result for tripartite 3-graphs

Abstract

Mantel's theorem says that among all triangle-free graphs of a given order the balanced complete bipartite graph is the unique graph of maximum size. We prove an analogue of this result for 3-graphs. Let $K_4^{-}=\{123,124,134\}$, $F_6=\{123,124,345,156\}$ and $\mathcal{F}=\{K_4^{-},F_6\}$: for $n\ne 5$ the unique $\mathcal{F}$-free 3-graph of order $n$ and maximum size is the balanced complete tripartite 3-graph $S_3(n)$ (for $n=5$ it is $C_5^{(3)}=\{123,234,345,145,125\}$). This extends an old result of Bollobás that $S_3(n)$ is the unique 3-graph of maximum size with no copy of $K_4^{-}=\{123,124,134\}$ or $F_5=\{123,124,345\}$.

12 pages