Extremal hypergraph theory

Extremal hypergraph theory asks how many hyperedges a hypergraph can have under a forbidden-configuration condition. For a fixed $r$-uniform hypergraph $F$, its extremal number ${\mathrm{ex}}_r(n,F)$ is the maximum number of hyperedges in an $n$-vertex $r$-uniform hypergraph containing no copy of $F$.

For $r=2$, this is ordinary extremal graph theory. For $r\ge 3$, pairwise adjacency no longer captures how vertices participate jointly, and even natural small forbidden configurations lead to difficult problems. The normalized limiting edge proportion is the Turán density. Thus hypergraph questions extend graph extremal problems while retaining genuinely higher-order incidence information.

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.

For sufficiently large vertex count $n$, 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. The unrounded positive lower bound is asserted for sufficiently large $n$.

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.