The general hypergraph Turán problem: determining $\operatorname{ex}(n,\mathscr{L})$ and extremal structures for forbidden families of uniform hypergraphs

For ordinary graphs, the Erdős–Stone–Simonovits theorem reduces the extremal number $\operatorname{ex}(n,\mathscr{L})$ of any forbidden family $\mathscr{L}$ to a single parameter, the minimum chromatic number of a member of $\mathscr{L}$, and the corresponding supersaturation and stability theory is essentially complete. In their 1983 paper "Supersaturated graphs and hypergraphs", Paul Erdős and Miklós Simonovits built the supersaturation machinery for hypergraphs but explicitly acknowledged that the behavior of $\operatorname{ex}(n,\mathscr{L})$ for general forbidden hypergraph families is complicated and poorly understood, with even elementary cases unsolved. This problem formulates that acknowledged open territory as the general hypergraph Turán problem: develop a theory that, for a forbidden family $\mathscr{L}$ of $k$-uniform hypergraphs ($k\ge 3$), determines the extremal number $\operatorname{ex}(n,\mathscr{L})$ — equivalently, where the limit exists, the Turán density — together with the extremal structures. The problem remains open: even the extremal density of the tetrahedron $K_4^3$, the smallest nontrivial 3-uniform instance, posed by Turán in the 1940s and carrying an Erdős prize, is still unknown.

Background

An $h$-uniform hypergraph (or $h$-graph) is a pair $H=(V,E)$ whose hyperedges are $h$-element subsets of the vertex set $V$; ordinary graphs are the case $h=2$. For a family $\mathscr{L}$ of forbidden $h$-uniform hypergraphs, the extremal number $\operatorname{ex}(n,\mathscr{L})$ is the maximum number of hyperedges in an $n$-vertex $h$-graph containing no member of $\mathscr{L}$ as a subhypergraph, and an $h$-graph is called supersaturated when it has more than $\operatorname{ex}(n,\mathscr{L})$ hyperedges. For graphs, extremal theory is essentially complete in the non-degenerate regime: Turán's theorem determines $\operatorname{ex}(n,K_{p+1})$ exactly, and the Erdős–Stone–Simonovits theorem determines $\operatorname{ex}(n,\mathscr{L})$ asymptotically through $\min_{L\in\mathscr{L}}\chi(L)$, the minimum chromatic number among the forbidden graphs (the chromatic number being the least number of colors needed to color the vertices so that no edge is monochromatic). Rademacher-type supersaturation results then quantify how many forbidden subgraphs must appear per unit of edge excess above the extremal threshold, and stability theorems assert that near-extremal graphs must resemble the Turán graph $T^{n,p}$, the complete $p$-partite graph on $n$ vertices with parts as equal as possible.

For $h\ge 3$ no comparable theory exists. The classical benchmark of Erdős (1964) gives $\operatorname{ex}\left(n,K_h^{(h)}(m,\ldots,m)\right)=O\!\left(n^{\,h-1/m^{h-1}}\right)$ for the complete $h$-partite $h$-graph with $h$ vertex classes of size $m$ (whose hyperedges are the $h$-tuples meeting each class exactly once), and this remains essentially the strongest general-type result. The 1983 paper of Erdős and Simonovits contributed general supersaturation theorems for hypergraphs (an additive excess of order $n^h$ above the extremal threshold forces polynomially many forbidden copies), a recursion $\operatorname{ex}(n,L^{(r)})\le c\,n^{\,h(1-1/r)+1/r}\operatorname{ex}(n,L)^{1/r}$ relating the extremal number of an auxiliary lifted $h$-graph $L^{(r)}$, built from an $(h-1)$-graph $L$ by enlarging its hyperedges with fresh vertices, to that of $L$ itself, and graph-side stability; but it explicitly left open the determination of $\operatorname{ex}(n,\mathscr{L})$ itself for general forbidden hypergraph families, noting that knowledge of its behavior was poor and that even elementary extremal problems in the area were unsolved. Where the density limit $\pi(F)=\lim_{n\to\infty}\operatorname{ex}(n,F)/\binom{n}{h}$ exists (its existence is classical), determining $\pi(F)$ is called the hypergraph Turán problem, initiated by Turán in the 1940s. The most famous instance is the tetrahedron $K_4^3$, the 3-uniform hypergraph on 4 vertices whose edges are all 4 triples, for which Turán conjectured an explicit construction; the best known upper bounds come from flag algebras, a computer-assisted semidefinite-programming method introduced by Razborov that certifies density upper bounds for small hypergraphs. Recent years produced strong partial advances — a full asymptotic theory for bounded-degree expansions (the $k$-expansion of a graph $G$ is the $k$-uniform hypergraph obtained by enlarging each edge of $G$ with $k-2$ fresh vertices, with distinct edges receiving disjoint sets of fresh vertices; Keevash–Lifshitz–Long–Minzer 2025), realizability of every rational exponent by some forbidden family (Fitch 2019), and container-based extensions of the supersaturation framework (the container method counts families of discrete structures by grouping them into few supersets called containers; Ferber–McKinley–Samotij 2018) — yet authoritative sources from 2019, 2022, and 2025 all reiterate that no general determination, and not even the value $\pi(K_4^3)$, is known.

Problem Statement

Develop a general theory of extremal numbers for forbidden families of uniform hypergraphs, playing the role for uniformity $k\ge 3$ that the Erdős–Stone–Simonovits theorem and the Erdős (1964) multipartite bound play for graphs: given a finite forbidden family $\mathscr{L}$ of $k$-uniform hypergraphs, determine $\operatorname{ex}(n,\mathscr{L})$ asymptotically, that is, determine the Turán density $\pi(\mathscr{L})=\lim_{n\to\infty}\operatorname{ex}(n,\mathscr{L})/\binom{n}{k}$ where the limit exists (for a single forbidden hypergraph $F$ this is the classical Turán density $\pi(F)$), together with the structure of the extremal or near-extremal hypergraphs. This is the acknowledged open territory of Erdős–Simonovits (1983). The task is resolved by any one of the following independently sufficient outcomes, each of which settles a distinct part of the program while the remainder stays open: (a) an exact determination of the tetrahedron density $\pi(K_4^3)$, the flagship precisely-formulated instance; (b) a general theorem determining $\operatorname{ex}(n,\mathscr{L})$ asymptotically, together with the extremal structure, for a named infinite class of forbidden families of $k$-uniform hypergraphs whose asymptotic determination is not already available in the cited literature; (c) a general theorem determining $\operatorname{ex}(n,\mathscr{L})$ asymptotically, together with the structure of the extremal or near-extremal hypergraphs, for arbitrary finite forbidden families $\mathscr{L}$ of $k$-uniform hypergraphs. The relevant landscape ranges from the classical benchmark $\operatorname{ex}\left(n,K_h^{(h)}(m,\ldots,m)\right)=O\!\left(n^{\,h-1/m^{h-1}}\right)$ of Erdős (1964) and the extremal numbers of bounded-degree expansions settled by Keevash–Lifshitz–Long–Minzer (2025) to the flagship precisely-formulated open instance, Turán's tetrahedron problem: determine $\pi(K_4^3)$, the extremal edge density of 3-uniform hypergraphs containing no tetrahedron, whose value has remained unknown since Turán posed it in the 1940s despite flag-algebra upper bounds.

References

1. Paul Erdős and Miklós Simonovits, "Supersaturated graphs and hypergraphs", Combinatorica 3(2) (1983), 181–192. DOI: 10.1007/bf02579292. https://doi.org/10.1007/bf02579292
2. P. Erdős, "On extremal problems of graphs and generalized graphs", Israel Journal of Mathematics 2(3) (1964), 183–190. DOI: 10.1007/bf02759942. https://doi.org/10.1007/bf02759942
3. Peter Keevash, "Hypergraph Turán problems", Surveys in Combinatorics 2011, London Mathematical Society Lecture Note Series 392, Cambridge University Press, 83–140. DOI: 10.1017/cbo9781139004114.004. https://doi.org/10.1017/cbo9781139004114.004
4. Asaf Ferber, Gweneth McKinley, and Wojciech Samotij, "Supersaturated Sparse Graphs and Hypergraphs", International Mathematics Research Notices 2020(2) (2020; published online 2018), 378–402. DOI: 10.1093/imrn/rny030. https://doi.org/10.1093/imrn/rny030
5. József Balogh, Felix Christian Clemen, and Bernard Lidický, "Solving Turán's Tetrahedron Problem for the ℓ2-Norm", Journal of the London Mathematical Society 106(1) (2022), 60–84. DOI: 10.1112/jlms.12568; arXiv:2108.10408. https://doi.org/10.1112/jlms.12568
6. Christian Reiher, "Extremal problems in uniformly dense hypergraphs", European Journal of Combinatorics 88 (2020), article 103117. DOI: 10.1016/j.ejc.2020.103117; arXiv:1901.04027. https://arxiv.org/abs/1901.04027
7. Victor Falgas-Ravry, Klas Markström, and Yi Zhao, "Triangle-degrees in graphs and tetrahedron coverings in 3-graphs", arXiv:1901.09560 (2019). https://arxiv.org/abs/1901.09560
8. Dhruv Mubayi and Jacques Verstraëte, "A survey of Turán problems for expansions", arXiv:1505.08078 (2015). https://arxiv.org/abs/1505.08078
9. Peter Keevash, Noam Lifshitz, Eoin Long, and Dor Minzer, "Turán Problems for Expanded Hypergraphs", Combinatorica 45(3), article 27 (2025). DOI: 10.1007/s00493-025-00152-4. https://doi.org/10.1007/s00493-025-00152-4
10. Matthew Fitch, "Rational exponents for hypergraph Turan problems", Journal of Combinatorics 10(1) (2019). DOI: 10.4310/joc.2019.v10.n1.a3; arXiv:1607.05788. https://arxiv.org/abs/1607.05788
11. Michelle Delcourt and Luke Postle, "The limit in the (k+2,k)-Problem of Brown, Erdős and Sós exists for all k at least 2", Proceedings of the American Mathematical Society (2024). DOI: 10.1090/proc/16668; arXiv:2210.01105. https://doi.org/10.1090/proc/16668