A problem of Turán. Turán observed that dividing the vertices into three equal parts $X_1,X_2,X_3$, and taking the edges to be those triples that either have exactly one vertex in each part or two vertices in $X_i$ and one vertex in $X_{i+1}$ (where $X_4=X_1$) shows that\[\mathrm{ex}_3(n,K_4^3)\geq\left(\frac{5}{9}+o(1)\right)\binom{n}{3}.\]This is probably the truth. The current best upper bound is\[\mathrm{ex}_3(n,K_4^3)\leq 0.5611666\binom{n}{3},\]due to Razborov [Ra10].

See also [712] for the general case.

View the LaTeX source

This page was last edited 05 October 2025.