On local Turán problems

Abstract

Since its formulation, Turán's hypergraph problems have been among the most challenging open problems in extremal combinatorics. One of them is the following: given a $3$-uniform hypergraph $\mathcal{F}$ on $n$ vertices in which any five vertices span at least one edge, prove that $|\mathcal{F}|\ge (1/4-o(1))\left(\genfrac{}{}{0ex}{}{n}{3}\right)$. The construction showing that this bound would be best possible is simply $\left(\genfrac{}{}{0ex}{}{X}{3}\right)\cup \left(\genfrac{}{}{0ex}{}{Y}{3}\right)$ where $X$ and $Y$ evenly partition the vertex set. This construction has the following more general $(2p+1,p+1)$-property: any set of $2p+1$ vertices spans a complete sub-hypergraph on $p+1$ vertices. One of our main results says that, quite surprisingly, for all $p>2$ the $(2p+1,p+1)$-property implies the conjectured lower bound.