Reduced hypergraph method (Reiher–Rödl–Schacht) — using the hypergraph regularity/counting lemma to reduce uniform Turán density problems for k-graphs to finite extremal problems about reduced hypergraphs

Statement

The problem this technique attacks. For a $k$-uniform hypergraph $F$, Erdős and Sós (1980s) asked for the uniform Turán density $\pi_u(F)$: the infimum of $d$ such that every sufficiently large $k$-graph $H$ that is *uniformly $d$-dense* — meaning every vertex subset $U\subseteq V(H)$, not just $V(H)$ itself, spans at least $d\binom{|U|}{k}-\eta|V(H)|^k$ edges (any $\eta>0$, $H$ large enough) — is forced to contain a copy of $F$. Formally, following Definition 1.1 of Reiher's survey (arXiv:1901.04027) for the $k=3$ case: $H=(V,E)$ is uniformly $(d,\eta)$-dense if $|U^{(3)}\cap E|\ge d\binom{|U|}{3}-\eta|V|^3$ for all $U\subseteq V$, and $$\pi_u(F)=\sup\Big\{d\in[0,1]: \text{for every }\eta>0,\ n\in\mathbb N\text{ there is an }F\text{-free, uniformly }(d,\eta)\text{-dense }H\text{ with }|V(H)|\ge n\Big\}.$$ This is a strictly stronger local-density requirement than the classical Turán density $\pi(F)$ (which only bounds $|E(H)|/\binom{|V(H)|}{3}$, i.e. it constrains the density of $H$ as a whole, not of every large subset) — hence $\pi_u(F)\le\pi(F)$ always, and the gap between them is exactly what makes $\pi_u$ interesting and much harder.

The reduced-hypergraph method (Reiher–Rödl–Schacht, ~2016–2019) is the machinery that makes $\pi_u(F)$ *computable* (or at least attackable) for specific $F$ by converting it into a finite combinatorial problem about small auxiliary objects called reduced hypergraphs, at the cost of running the full hypergraph regularity method (regularity lemma + counting lemma) once, as a black box, to prove the reduction is valid.

Reduced hypergraphs (Definition 3.1, arXiv:1901.04027). Fix a finite index set $I$. For every pair of distinct indices $i,j\in I$ fix a finite nonempty vertex class $P_{ij}=P_{ji}$ (pairwise disjoint across index-pairs), and for every triple $ijk\in\binom{I}{3}$ fix a tripartite 3-uniform hypergraph $A_{ijk}$ on $(P_{ij},P_{ik},P_{jk})$, called a constituent. The union $A$ of all the $P_{ij}$'s (as vertex set) and all $E(A_{ijk})$'s (as edge set) is a reduced hypergraph with index set $I$, vertex classes $P_{ij}$, constituents $A_{ijk}$. $A$ is called $(d,\cdot)$-dense if every constituent has edge density $\ge d$; $(d,\cdot\cdot)$-dense if a min-vertex-degree condition holds inside every constituent; $(d,\cdot\cdot\cdot)$-dense if a min-pair-degree condition holds — these three grades correspond exactly to the three escalating "crossing-density" notions ($A,B,C$-triple density / vertex-vs-pair density / pair-vs-pair density) that Reiher–Rödl–Schacht show are all *provably equal* to $\pi_u(F)$ itself (their equation (1.3) and the surrounding discussion), so the choice of grade is a technical convenience, not a change of target quantity.

Reduced maps and the reduction theorem (Definition 3.2, Theorem 3.3). A reduced map from $F$ to $A$ is a pair $(\lambda,\varphi)$ with $\lambda:V(F)\to I$ and $\varphi$ sending each pair of $F$-vertices covered by an $F$-edge to a vertex of the appropriate $P_{\lambda(u)\lambda(v)}$, such that every edge $uvw\in E(F)$ maps to a genuine edge of the constituent $A_{\lambda(u)\lambda(v)\lambda(w)}$. If such a map exists, $A$ contains a reduced image of $F$; otherwise $A$ is $F$-free. Reiher's Theorem 3.3: $$\pi_\star(F)=\sup\Big\{d\in[0,1]:\text{for every }m\in\mathbb N\text{ there is a }(d,\star)\text{-dense, }F\text{-free reduced hypergraph with }m\text{ indices}\Big\}$$ for each of the three density grades $\star$. In words: computing the (uniform) Turán density of $F$ is equivalent to a purely finite/combinatorial extremal problem about how densely one can pack constituents into a reduced hypergraph while staying $F$-free — no limits over $n\to\infty$ or $\eta\to0$ remain once you're inside the reduced world.

Facts

- Flagship theorem proved by this method: $\pi_u(K_4^{(3)-})=1/4$ (Reiher–Rödl–Schacht, "On a Turán problem in weakly quasirandom 3-uniform hypergraphs," *J. Eur. Math. Soc.* 20 (2018), 1139–1159, arXiv:1602.02290), settling a ~30-year-old Erdős–Sós question. Independently and almost simultaneously proved by a *different* method — Razborov's computer-assisted flag algebras — by Glebov–Král'–Volec (*Israel J. Math.* 211 (2016), 349–366, arXiv:1303.7372). See this wiki's 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) for the full writeup; the matching lower-bound construction in both proofs is the same random-tournament / cyclic-triangle "palette" gadget (§2 below). - The full tetrahedron $K_4^{(3)}$ is still open at the coarsest (Definition-1.1) density level. Rödl's 2-coloring construction (color each pair red/green uniformly at random; edge $ijk$ ($i<j<k$) iff colors of $ij,ik$ disagree) gives $\pi_u(K_4^{(3)})\ge 1/2$; Conjecture 1.3 (Reiher's survey) is that this is tight. What *is* proved (Theorem 1.4, via the reduced-hypergraph method) is the analogous statement $=1/2$ for the *finer* (pair-vs-pair, "$\pi_{\bullet\bullet}$"-grade) density notion — a genuinely weaker theorem than the full conjecture, since $\pi_{\bullet\bullet}(F)\ge\pi_u(F)$ in general. - Jump phenomenon. Reiher–Rödl–Schacht, "Hypergraphs with vanishing Turán density in uniformly dense hypergraphs," *J. London Math. Soc.* 97 (2018), 77–97, prove $\pi_u(F)\in(0,1/27)$ is impossible for any 3-graph $F$ — the uniform Turán density spectrum "jumps" straight from $0$ to $\ge1/27$ (arXiv:1901.04027, Theorem 2.2, via the "palette" order/coloring framework: $\pi_u(F)=0$ iff $F$ admits a vertex-ordering + 3-coloring of its shadow forced to be "rainbow-in-order" on every edge). - The extremal (lower-bound) constructions are always "palettes." A palette is a set $P\subseteq\Phi^3$ of allowed ordered color-triples over a finite color alphabet $\Phi$; randomly color all pairs of an ordered vertex set from $\Phi$ and declare $xyz$ ($x<y<z$) an edge iff its induced color-triple lies in $P$ — this always yields a uniformly-quasirandom hypergraph at density $|P|/|\Phi|^3$ a.a.s. Known examples give $\pi_u(K_4^{(3)-})\ge1/4$ (2-color orientation palette), $\pi_u(S_k)\ge (k^2-5k+7)/(k-1)^2$ for stars (cones over $K_k$), $\pi_u(K_{r+2}^{(3)})\ge (r-1)/r$, and, via the finer pair-density grade and symmetric palettes, $\pi_u(K_{11}^{(3)})=\cdots=\pi_u(K_{16}^{(3)})=2/3$ combined with an upper bound $\pi_{\bullet\bullet}(K_{2r})\le (r-2)/(r-1)$ (Theorem 2.9) that is sharp in surprisingly many small cases. A 2024+ paper, "Palettes determine uniform Turán density" (arXiv:2408.09643, cited but not primary-read here — see 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)), proves palettes are always optimal, turning this ad hoc recipe into a universal lower-bound principle. - Generalization beyond $k=3$ is hard and recent. As of arXiv:2508.20696 ("Uniform Turán density beyond 3-graphs," 2025, abstract directly fetched and quoted): "infinitely many non-zero values [are] known for $r=3$, a single non-zero value known for $r=4$ and none for $r\ge5$" — that paper supplies the first families of exact values $\pi_u(F)=1/4$ and $\pi_u(F)=\binom{r}{2}^{-\binom r2}$ for every $r\ge3$, using the same reduced-hypergraph philosophy generalized to $k$-graphs (indexed there and elsewhere as $\pi_{k-2}(F)$, the finest of a hierarchy $\pi_0(F)=\pi(F)\ge\pi_1(F)\ge\cdots\ge\pi_{k-2}(F)$ of increasingly strong uniform-density notions).

Technique

WHEN it applies. Reach for the reduced hypergraph method when: 1. The target quantity is (some grade of) the uniform Turán density $\pi_u(F)$, or more generally an extremal density defined by a *hereditary* local-density condition (every large vertex subset, or every dense pair/tuple-structure, must be dense) rather than plain global edge density. 2. You already have (or can construct) a candidate extremal value $d$ via a palette construction (§Facts above) for the lower bound, and need to prove the matching upper bound: that every uniformly-$(d+\varepsilon)$-dense large $H$ must contain $F$. 3. $F$ is small enough (few vertices/edges) that the resulting finite reduced-hypergraph extremal problem is tractable by hand or computer search — this is the same regime where flag algebras (Razborov) are the natural competing tool; the reduced-hypergraph route trades flag algebras' semidefinite-programming automation for a human-checkable, generalizable combinatorial argument (and, per Reiher's survey, has become the tool of choice for the whole follow-up research program after the $K_4^{(3)-}$ base case).

WHY it works (the mechanism). The proof of the reduction theorem $\pi_\star(F)=\pi^{rd}_\star(F)$ splits into two directions with very different flavors: - Easy direction ($\pi^{rd}_\star(F)\le\pi_\star(F)$, Proposition 3.4). Given a dense $F$-free reduced hypergraph $A$ on $m$ indices, *blow up* each vertex class $P_{ij}$ into an independent-random $(\delta,|P_{ij}|^{-1})$-quasirandom bipartite graph between vertex groups $V_i,V_j$, and read off a genuine 3-graph $H$ by declaring $xyz$ an edge (for $x\in V_i,y\in V_j,z\in V_k$) iff the random colors $\varphi_{ij}(xy),\varphi_{ik}(xz),\varphi_{jk}(yz)$ form an edge of the constituent $A_{ijk}$. The triangle counting lemma for quasirandom tripartite graphs transfers $A$'s density and $F$-freeness (any embedding of $F$ into $H$ would project down, via which vertex-group each image vertex lands in, to a reduced map from $F$ into $A$) directly to $H$. This direction needs only quasirandom-graph counting, not the full hypergraph regularity machinery. - Hard direction ($\pi_\star(F)\le\pi^{rd}_\star(F)$, Proposition 5.4) — this is where "hypergraph regularity" enters. Apply the hypergraph regularity lemma (Theorem 5.2, due to Frankl–Rödl and refined by Rödl–Skokan/Gowers/Nagle–Rödl–Schacht) to an arbitrary large uniformly-dense $H$: it decomposes $V(H)$ into $t$ parts and, for each pair of parts, the bipartite edge set into $\ell$ quasirandom pieces, such that $H$ is $\delta_3$-regular with respect to all but a small fraction of the resulting triads (the tripartite graphs formed by picking one quasirandom piece from each of the three relevant part-pairs). Build a reduced hypergraph $A$ whose index set is exactly $[t]$, whose vertex classes are the $\ell$ regular pieces $P_{ij}^\alpha$, and whose constituent $A_{ijk}$ contains $\{P_{ij}^\alpha,P_{ik}^\beta,P_{jk}^\gamma\}$ exactly when $H$'s relative density on that triad is $\ge d_3$. $H$'s uniform density transfers (via the regularity lemma's density-preservation) to $A$'s density; the delicate remaining step is that a reduced map from $F$ into $A$ (which only guarantees the *triads* are individually dense, not literally "full") still yields an actual copy of $F$ inside $H$ — this final step is exactly the hypergraph counting lemma (Theorem 5.3, "Embedding Lemma," built on Nagle–Poerschke–Rödl–Schacht's counting theorem): dense regularity on all of $F$'s triads forces at least a $\frac12 d_3^{e(F)}\ell^{-|B_F|}$-fraction of the naive homomorphism count to actually be present, which is enough to guarantee an injective copy for large enough part sizes. So the entire "hardness" of the reduced hypergraph method is imported wholesale from the regularity + counting lemma pair — the reduced hypergraph itself is nothing more than an explicit combinatorial encoding of one hypergraph-regularity-lemma decomposition.

The reusable recipe (recombination guidance for a solver). 1. Guess the extremal density $d$ for your target $F$ via a palette construction (order the vertices, pick a small color alphabet $\Phi$, choose which color-triples become edges) — this is almost always the fastest way to get a strong candidate answer, and per arXiv:2408.09643 it is now known to always be *tight* when the true optimum exists among "nice" constructions. 2. Reformulate "$\pi_u(F)\ge d+\varepsilon\implies F\subseteq H$" as a finite reduced-hypergraph statement: show that every sufficiently large $(d+\varepsilon,\star)$-dense reduced hypergraph (choose the density grade $\star$ matching what your argument naturally controls — vertex-set density, vertex-vs-pair, or pair-vs-pair) contains a reduced image of $F$. This step is a finite combinatorial/Ramsey-flavored argument about constituents (tripartite 3-graphs) glued along shared bipartite vertex classes — often amenable to direct combinatorial case analysis (as in the $K_4^{(3)-}$ proof: show every dense-enough reduced hypergraph has an index whose "link" constituent contains a triangle) or to computer search for small index sets. 3. Invoke Theorem 3.3 as a black box to transfer the finite reduced-hypergraph statement back up to the genuine uniform-Turán-density statement about arbitrary large $H$ — this step costs nothing extra once Theorem 3.3 (i.e. the regularity lemma + counting lemma machinery) is taken as already established for your uniformity $k$. 4. Robustness bookkeeping (§4 of the survey, Lemmas 4.1/4.2): because the regularity lemma only delivers *approximate* regularity (a few irregular/exceptional triads, a few sparse vertices/pairs), you need the finite reduced-hypergraph statement from step 2 to be robust to deleting a small fraction of vertices/pairs from $A$ — this is usually a routine (if fiddly) perturbation argument, not a source of new mathematical difficulty. 5. Escalate to a finer density grade (crossing-triple $\to$ vertex-vs-pair $\to$ pair-vs-pair) when the coarsest grade's reduced-hypergraph problem resists direct attack — finer grades give *more* structural information about $A$ (min-degree rather than just density conditions on constituents) at the cost of proving a *formally weaker* theorem (since $\pi_{\bullet\bullet}(F)\ge\pi_u(F)$), exactly the tradeoff exploited for the tetrahedron (Theorem 1.4 proves the pair-vs-pair version, Conjecture 1.3 for the base uniform-density version remains open). 6. When targeting $k\ge4$-uniform $F$, expect the reduced-hypergraph bookkeeping to explode in complexity (the regularity lemma for rank-$\ge4$ hypergraphs requires a full hierarchy of nested regular partitions, not just one level) — per arXiv:2508.20696 this is precisely why so few exact values were known for $r\ge4$ as of 2025, and why new constructions there are treated as notable results in their own right.

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 sibling page covering the more classical Frankl–Rödl/Rödl–Skokan/Nagle–Rödl–Schacht/Gowers/Tao regularity-counting-removal-lemma strand, used for ordinary Turán density, corners/Szemerédi-type, and Gowers-uniformity-norm problems; this page's reduction theorem (Theorem 3.3) is built directly on top of that page's Regularity Lemma (Theorem 5.2 here) and Counting Lemma (Theorem 5.3 here) as a black box, but targets the strictly different, *hereditarily local* uniform-Turán-density quantity $\pi_u$, not the removal lemma. - 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 flagship worked example ($\pi_u(K_4^{(3)-})=1/4$), including both the reduced-hypergraph proof route documented in depth on this page and the independent flag-algebra route. - Erdős #500 — Turán density of the tetrahedron $K_4^{3}$ — the (ordinary, non-uniform) Turán density of the tetrahedron $K_4^{(3)}$, a related but formally different open problem in the same "dense 3-graph extremal" universe; contrast with this page's Conjecture 1.3 ($\pi_u(K_4^{(3)})\overset{?}{=}1/2$), which is the *uniform*-density analogue and is also open. - Supersaturation theorem — density strictly above the Turán threshold forces Ω(n^h) copies, not just one (Erdős–Simonovits 1983) — a related density-forcing philosophy (many copies of a dense pattern force one exact copy elsewhere); the counting lemma underlying this page's Theorem 5.3 is a quantitative supersaturation-type statement for regular triads. - Razborov flag algebras (no dedicated wiki page yet) — the competing computer-assisted semidefinite-programming technique that independently re-derived the $K_4^{(3)-}$ base case (Glebov–Král'–Volec) and remains the main alternative tool for uniform/ordinary Turán-density problems where a human-checkable reduced-hypergraph argument has not yet been found.