Extremal hypergraph theory

Extremal hypergraph theory studies the largest or smallest possible size of a hypergraph under prescribed forbidden-subhypergraph or covering conditions. It generalizes extremal graph theory. The Turán density describes the asymptotic maximum edge proportion for a fixed uniform forbidden hypergraph.

With $r$ balanced cyclically ordered vertex classes and $2\le \ell \le r+1$, include an $\ell$-set if some start has at least $k+1$ vertices in its first $k$ classes for every $1\le k\le \ell -1$. The cycle lemma implies every $(r+1)$-set contains an edge. Its asymptotic density is $((\ell -1)/r{)}^{\ell -1}$; taking the hypergraph complement gives a lower bound for the Turán density of a complete uniform hypergraph.

For a fixed $\ell$-uniform forbidden hypergraph $F$, its Turán density is the limit of $\mathrm{ex}(n,F)/\left(\genfrac{}{}{0ex}{}{n}{\ell }\right)$. Averaging over smaller vertex subsets shows these normalized extremal numbers are nonincreasing, so the limit exists. For ordinary graphs, the Erdős-Stone theorem determines it from the chromatic number.

For the complete $\ell$-uniform hypergraph $K_r^{\ell }$, with $r\ge \ell \ge 2$, the bound is $\pi (K_r^{\ell })\le 1-1/\left(\genfrac{}{}{0ex}{}{r-1}{\ell -1}\right)$. In the complementary covering formulation, every $r$-set containing an edge forces asymptotic edge density at least $1/\left(\genfrac{}{}{0ex}{}{r-1}{\ell -1}\right)$. It follows from clique-extension incidence inequalities and Cauchy-Schwarz inequality estimates on link degrees.