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.

For all sufficiently large $n$, the extremal number of the Fano plane as a three-uniform hypergraph is the displayed count of all triples crossing a balanced bipartition. The plane has no Property B, so this construction avoids it. A stability argument makes near-extremal Fano-free hypergraphs nearly bipartite; vertex deletion obtains high minimum degree. Optimizing the approximate bipartition and applying Fano completion through three matchings then rules out all internal triples. The large-order qualification matters: for $n=5,6$ the complete hypergraph has no Fano copy but exceeds the displayed count.

For every $\rho >0$, some $\delta >0$ makes every sufficiently large Fano-free three-uniform hypergraph of density at least $3/4-\delta$ admit a partition with at most $\rho n^3$ internal triples. The argument compares four hypergraph link graphs around a tetrahedron. Forbidden rainbow perfect matchings in their edge-coloured union force an approximate pattern with multiplicity two within the parts and four between them. A positive internal triple density would produce a complete tripartite six-vertex template, and its pairs together with a link vertex would complete a Fano plane.

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.

Normalized hypergraph extremal numbers decrease under vertex sampling and converge to Turán density. At a fixed sample size where the extremal density is close to that limit, excess density forces a positive fraction of samples to contain $H$. Counting incidences of copies and samples proves the displayed lower bound. Shrinking $\delta$ also handles the finitely many small orders when the required count is rounded down.

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.