Uniform Turán density π_u(F) — Turán problem refined to uniformly-dense (quasirandom) host hypergraphs (Erdős–Sós, ~1990)

Statement

Ordinary Turán density of a $k$-uniform hypergraph $F$: $\pi(F)=\lim_{n\to\infty}\mathrm{ex}(n,F)/\binom{n}{k}$, the limiting maximum edge-density an $F$-free host can have (well-defined/monotone by Katona–Nemetz–Simonovits averaging). For $k=2$ this is fully solved by Erdős–Stone ($\pi(F)=\tfrac{\chi(F)-2}{\chi(F)-1}$), but for $k\ge3$ almost nothing is known exactly — already the 3-vertex-deleted tetrahedron $K_4^{(3)-}$ and the full tetrahedron $K_4^{(3)}$ are open or were open for decades (Erdős #500 — Turán density of the tetrahedron $K_4^{3}$).

Uniform Turán density $\pi_u(F)$ (Reiher's notation: $\pi(F)$ with an underline; called $\overline{\pi}$ or $\pi_u$ elsewhere) restricts attention to host hypergraphs that are *quasirandom/uniformly dense*, i.e. that cannot cheat by concentrating all their density on a small vertex subset. For real $d\in[0,1]$, $\eta>0$, a $k$-uniform hypergraph $H=(V,E)$ is uniformly $(d,\eta)$-dense if $$|U^{(k)}\cap E| \;\ge\; d\binom{|U|}{k} - \eta|V|^k \qquad \text{for every } U\subseteq V.$$ (This is the natural generalization of Chung–Graham–Wilson graph quasirandomness — "every linear-size vertex subset spans about the right number of edges" — to hypergraphs; sometimes called *weak $(d,\eta)$-quasirandomness*.) Then $$\pi_u(F) \;=\; \sup\Big\{\, d\in[0,1] : \forall\,\eta>0,\ \forall\, n\in\mathbb N,\ \exists\ \text{an } F\text{-free, uniformly } (d,\eta)\text{-dense } H \text{ with } |V(H)|\ge n \,\Big\}.$$ Equivalently, $\pi_u(F)$ is the infimum $d$ such that every sufficiently large uniformly-$(d+\varepsilon,\eta)$-dense hypergraph (small enough $\eta$) is forced to contain $F$. Trivially $\pi_u(F)\le\pi(F)$ (a uniform-density lower bound is a strictly stronger requirement on the host than a global density lower bound), and the gap can be strict — e.g. $\pi(K_4^{(3)-})\in[2/7,\,0.2871]$ (open) but $\pi_u(K_4^{(3)-})=1/4$ exactly (solved).

Origin: proposed by Erdős and Sós, "On Ramsey–Turán type theorems for hypergraphs," *Combinatorica* 2 (1982), 289–295, and again in Erdős, "Problems and results on graphs and hypergraphs: similarities and differences" (1990) — motivated by the observation that the classical extremal constructions for hypergraph Turán problems (e.g. the Frankl–Füredi construction for $K_4^{(3)-}$) are *not* uniformly dense: they hide all their structure on a sparse subset, which feels like "cheating." Restricting to uniformly-dense hosts asks for the truly robust extremal density.

Facts

- Equivalent reformulations used for proofs (Reiher, arXiv:1901.04027, §1.3): $\pi_u(F)$ equals the analogous sup where the host must instead satisfy the *tripartite* condition $|\mathcal E(A,B,C)|\ge d|A||B||C|-\eta|V|^3$ for all $A,B,C\subseteq V$ (density between three vertex sets, not just within one) — proved equal to the Def-1.1 version in Reiher–Rödl–Schacht, "On a generalisation of Mantel's Theorem to Uniformly Dense Hypergraphs," *IMRN* 2018, Prop. 2.5. This tripartite form is the one actually used in proofs because it plugs directly into hypergraph-regularity counting lemmas. Two further, *strictly stronger*, refinements $\overline{\overline\pi}$ (vertex-set vs. pair-set density) and $\overline{\overline{\overline\pi}}$ (pair-set vs. pair-set density) are also defined and satisfy $\pi_u(F)\le\overline{\overline\pi}(F)\le\overline{\overline{\overline\pi}}(F)$; a further "triple-of-pairs" version turns out to *always vanish* and is discarded. Most of the literature's "uniform Turán density" results are about the first ($\pi_u$) or occasionally the second tier. - The gap / jump theorem: Reiher–Rödl–Schacht, "Hypergraphs with vanishing Turán density in uniformly dense hypergraphs," *J. London Math. Soc.* 97 (2018), 77–97 — proves $\pi_u(F)=0$ iff $F$'s vertices admit an enumeration $v_1,\dots,v_f$ and a 3-colouring $\{$red, blue, green$\}$ of the pairs covered by edges such that every hyperedge $\{v_i,v_j,v_k\}$ ($i<j<k$) is coloured $(\text{red},\text{blue},\text{green})$ on $(v_iv_j,v_iv_k,v_jv_k)$ (this is exactly "$F$ embeds into the singleton palette $\{(\mathrm{red,blue,green})\}$," density $1/27$ — see Technique below). Consequence: $\pi_u(F)\notin(0,\,1/27)$ for every 3-uniform $F$ — the value jumps straight from $0$ to $\ge 1/27$, with no intermediate values possible. - $1/27$ is tight: Reiher–Rödl–Schacht (and a later paper, "Hypergraphs with minimum positive uniform Turán density," *Israel J. Math.* (2023), arXiv:2105.09883) exhibit 3-graphs $F$ with $\pi_u(F)=1/27$ exactly, so the gap theorem's lower endpoint is achieved, not just a bound. - The founding solved case, $K_4^{(3)-}$ (broken tetrahedron): Erdős–Sós asked for $\pi_u(K_4^{(3)-})$; the tournament/cyclic-triangle construction (Rödl, following Erdős–Hajnal) gives $\pi_u(K_4^{(3)-})\ge 1/4$, and this is *tight*: $\pi_u(K_4^{(3)-})=1/4$, proved independently by Glebov–Král'–Volec (flag algebras, *Israel J. Math.* 211 (2016), arXiv:1303.7372) and by Reiher–Rödl–Schacht (hypergraph regularity method, *JEMS* 20 (2018), arXiv:1602.02290). Full write-up in this wiki: Uniform Turán density of the broken tetrahedron K_4^{(3)-} equals 1/4 (Erdős–Sós problem, solved 2013–2016 by two independent methods). - Other known exact values: $\pi_u(K_6^{(3)})=\pi_u(K_7^{(3)})=\pi_u(K_8^{(3)})=1/2$ and $\pi_u(K_{11}^{(3)})=\cdots=\pi_u(K_{16}^{(3)})=2/3$ (Reiher, "Some remarks on $\overline{\overline\pi}$," 2018, via the clique bound $\overline{\overline\pi}(K_{2r}^{(3)})\le\tfrac{r-2}{r-1}$ combined with matching palette lower bounds); $\pi_u(K_4^{(3)})\ge1/2$ (Rödl's random-2-colouring-of-pairs construction), conjectured $=1/2$, still open — the natural successor to the $K_4^{(3)-}$ result. A quantity $8/27$ was later shown to occur, and the values $\{0,\,1/27,\,4/27,\,1/4,\,8/27\}$ are the currently known/published achieved uniform Turán densities (arXiv:2407.05829, "Hypergraphs with uniform Turán density equal to $8/27$"; the earlier lower bound $\pi_u(C_5^{(3)})\ge4/27$ for the 5-cycle is in Reiher's survey, Example 2.5). - "Palettes determine uniform Turán density" (arXiv:2408.09643) proves that the palette construction (below) is *always* asymptotically optimal for $\pi_u$ — i.e. every extremal/near-extremal lower-bound witness can be taken to be a palette construction, turning what looked like an ad-hoc trick into the universal lower-bound method. The 2025 follow-up "Uniform Turán density — palette classification" (Kráľ, Kučerák, Lamaison, Tardos, arXiv:2505.17325) analyzes *which* rational numbers can arise as values of $\pi_u$ at all, i.e. classifies the achievable spectrum of the function $\pi_u$. - General $k\ge2$: the framework (uniform density, tripartite/pair/pair-set refinements, reduced hypergraphs) is developed for all $k$-uniform hypergraphs in Reiher–Rödl–Schacht, *IMRN* 2018 (arXiv cited as [28] in the survey); for $k=2$ (graphs) the theory degenerates back to the classical Erdős–Stone density since 2-uniform "uniform density" forces near-completeness on subsets in essentially the classical way.

Technique

When it applies: whenever you want to determine (or bound) the extremal density of an $F$-free hypergraph under the *extra* promise that the host is quasirandom on every linear-size vertex subset — i.e. whenever a classical Turán-type question is suspected to have a "sparse cheat" extremal construction (concentrating density on a small part) that feels non-robust, and you want the density forced by genuinely spread-out structure instead. It is specifically a $k\ge3$-uniform-hypergraph technique (for graphs the ordinary and uniform notions effectively coincide via Erdős–Stone).

Why it works — the two-sided mechanism:

1. **Lower bounds via *palette* constructions (Reiher, arXiv:1901.04027, §2). Fix a finite colour set $\Phi$ and a palette $P\subseteq\Phi^3$ (a set of "allowed" ordered colour-triples). Take a huge linearly ordered vertex set $(V,<)$, colour every pair $\varphi:\binom{V}{2}\to\Phi$ independently uniformly at random, and declare $\{x,y,z\}$ ($x<y<z$) to be a hyperedge iff $(\varphi(x,y),\varphi(x,z),\varphi(y,z))\in P$. If $P$ is $(d,\text{-})$-dense ($|P|\ge d|\Phi|^3$), this random hypergraph is a.a.s. uniformly $(d,\eta)$-dense for every $\eta>0$ (a Chernoff-bound / concentration argument, since edge-membership only depends on 3 independent random colours). Hence $\pi_u(F)\ge d$ whenever $F$ admits no "reduced map" into $P$** — i.e. there is *no* ordering of $V(F)$ and colouring of its covered pairs by $\Phi$ under which every hyperedge's ordered colour-triple lands in $P$. Checking "does $F$ embed into palette $P$" is a finite combinatorial search (over orderings and colourings of the small graph $F$), which is what makes these lower bounds concretely computable. Examples: the singleton palette $\{(\text{red},\text{blue},\text{green})\}$ over 3 colours is $(1/27,\text{-})$-dense and gives the $0$-vs-$\ge1/27$ gap theorem; the 2-colour palette $\{(r,g,r),(r,g,g),(g,r,r),(g,r,g)\}$ (equivalently, the random-tournament / cyclic-triangle construction) is $(1/4,\text{-})$-dense and gives $\pi_u(K_4^{(3)-})\ge1/4$; a $k$-vertex weighted-colour palette gives the $\pi_u(K_r^{(3)})$ family of lower bounds via classical Ramsey facts ($6\to(3)^2_2$, Chung–Graham). 2. **Upper bounds via the *hypergraph regularity method* (Gowers 2006; Rödl–Skokan; Nagle–Poerschke–Rödl–Schacht; used by Reiher–Rödl–Schacht throughout). The key structural fact is Theorem 3.3 (Reiher, arXiv:1901.04027): $\pi_u(F)$ equals the analogous supremum taken over finite reduced hypergraphs** — a bounded combinatorial gadget (an index set $I$, vertex classes $P_{ij}$ per pair of indices, and "constituent" tripartite hypergraphs $A_{ijk}$ per triple of indices, each required to be $d$-dense) that plays the role of the regularity-lemma "reduced graph" for triple systems. The regularity + counting lemmas for 3-uniform hypergraphs let you (a) blow a $d$-dense $F$-free reduced hypergraph *up* into a genuine uniformly-$(d,\eta)$-dense $F$-free hypergraph on $n$ vertices (giving $\pi_u^{\mathrm{rd}}(F)\le\pi_u(F)$ — the "easy" direction, essentially the same probabilistic mechanism as palette constructions but generalized to allow different local rules on different index-triples), and (b) conversely regularize *any* uniformly dense $F$-free $H$ down into a bounded-size reduced hypergraph that is still $F$-free (giving $\pi_u(F)\le\pi_u^{\mathrm{rd}}(F)$, the hard direction, via the hypergraph regularity + embedding lemma). Because $\pi_u^{\mathrm{rd}}(F)$ is now a statement about *finite* combinatorial gadgets, it can be attacked by direct combinatorial arguments (as in Reiher's own $\pi_u(K_4^{(3)})=0$-type sketches, §6) or fed to flag algebras (Razborov's SDP-based framework) as an alternative, computer-assisted route to the same upper bound — this is exactly the route Glebov–Král'–Volec used for $K_4^{(3)-}$, in parallel with Reiher–Rödl–Schacht's human/regularity proof.

How to actually use it to prove something (recipe): 1. To lower-bound $\pi_u(F)$: search (by hand or computer) over small colour alphabets $\Phi$ and palettes $P\subseteq\Phi^3$ for one that is $(d,\text{-})$-dense and into which $F$ admits *no* reduced map (no consistent ordering+colouring of $F$ landing entirely inside $P$); conclude $\pi_u(F)\ge d$. Try symmetric/weighted palettes and known Ramsey facts ($r\to(s)^t_c$) to push $d$ up (Examples 2.4, 2.7, 2.8 in Reiher's survey). 2. To upper-bound (or pin down exactly) $\pi_u(F)$: convert to the reduced-hypergraph question via Theorem 3.3, then either (a) find a direct combinatorial argument that every sufficiently dense $F$-free reduced hypergraph is small/structured (regularity-method route — reusable, human-checkable, generalizes), or (b) set up the corresponding flag-algebra SDP and solve numerically for a certificate (flag-algebra route — faster to get the *numerical* answer, good for conjecturing the right constant before a human proof exists). 3. Match the two bounds; if they coincide, $\pi_u(F)$ is determined exactly (as for $K_4^{(3)-}=1/4$). If a gap remains, the residual problem is where new work (as in "Beyond the broken tetrahedron," arXiv:2211.12747, pushing toward the still-open $\pi_u(K_4^{(3)})\overset{?}{=}1/2$) is targeted.

Related

- Hypergraph regularity / Gowers uniformity norms and density-increment arguments: quasirandom decomposition + counting/removal lemmas, and the iterative-density-increase route to Szemerédi-type theorems — the regularity/counting-lemma machinery (Gowers; Rödl–Skokan; Nagle–Poerschke–Rödl–Schacht) that supplies the reduced-hypergraph equivalence (Theorem 3.3) and hence every regularity-method upper bound on $\pi_u$. - Turán number ex(n,H): extremal edge-count for forbidden subgraphs — the classical (non-uniform) Turán density $\pi(F)$ that $\pi_u(F)$ refines/strengthens; $\pi_u(F)\le\pi(F)$ always, with the gap itself an interesting open-ended question per hypergraph. - Uniform Turán density of the broken tetrahedron K_4^{(3)-} equals 1/4 (Erdős–Sós problem, solved 2013–2016 by two independent methods) — the founding worked example, $\pi_u(K_4^{(3)-})=1/4$, with both the flag-algebra and regularity-method proof routes and the palette lower-bound construction laid out in full. - Erdős #500 — Turán density of the tetrahedron $K_4^{3}$ — Turán's tetrahedron problem $\pi(K_4^{(3)})$, the classical (non-uniform) sibling that the still-open $\pi_u(K_4^{(3)})\overset{?}{=}1/2$ conjecture sits next to; both are Erdős-favourite hypergraph-Turán questions where flag-algebra/SDP mining has stalled and the uniform-density ladder is the actively moving front. - Flag algebras (Razborov, *J. Symbolic Logic* 72 (2007)) — the computer-assisted SDP route that gives an independent, often faster, way to obtain the same upper bounds as the regularity method; used in parallel on $K_4^{(3)-}$ by Glebov–Král'–Volec. - Chung–Graham–Wilson graph quasirandomness — the $k=2$ ancestor notion that uniform $(d,\eta)$-density (Definition 1.1 above) directly generalizes to $k$-uniform hypergraphs.