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)

Statement

Let $K_4^{(3)-}$ (the broken tetrahedron) be the 3-uniform hypergraph on 4 vertices with 3 of the 4 possible triples as edges (i.e. $K_4^{(3)}$ with one hyperedge deleted).

Erdős and Sós (early 1980s) introduced the notion of uniform Turán density $\pi_u(F)$ for a 3-uniform hypergraph $F$: the infimum of $d$ such that every sufficiently large 3-uniform hypergraph $H$ that is *uniformly $d$-dense* — meaning every linear-sized vertex subset $U\subseteq V(H)$ (specifically $|U|\ge \delta|V(H)|$ for the relevant $\delta$) spans at least $d\binom{|U|}{3}$ edges — is forced to contain a copy of $F$. (This is a strictly stronger uniformity requirement than the classical Turán density, which only controls the density of $H$ itself, not of every large subset.)

Question (Erdős–Sós)

what is $\pi_u(K_4^{(3)-})$?

Facts

- Origin: Erdős and Sós posed the general uniform-Turán-density program in the 1980s; $K_4^{(3)-}$ was the first non-trivial case they highlighted, and it remained open for roughly three decades. - Answer: $\pi_u(K_4^{(3)-}) = 1/4$. - Two independent proofs, ~3 years apart: 1. Roman Glebov, Daniel Král', Jan Volec, "A problem of Erdős and Sós on 3-graphs," *Israel J. Math.* 211 (2016), 349–366 (announced 2013, arXiv:1303.7372) — via flag algebras (computer-assisted semidefinite-programming method of Razborov). 2. Christian Reiher, Vojtěch Rödl, Mathias Schacht, "On a Turán problem in weakly quasirandom 3-uniform hypergraphs," *J. Eur. Math. Soc.* 20 (2018), 1139–1159 (arXiv:1602.02290) — via the hypergraph regularity method, giving a human-checkable (non-computer-assisted) proof and, as a bonus, an *ordered* version of the theorem. - This was the first genuinely non-trivial exact uniform-Turán-density determination after the Erdős–Sós program had stood open for ~30 years (per the framing in the "Palettes determine uniform Turán density" survey, arXiv:2408.09643). - Extremal (lower-bound) construction: a random tournament on the vertex set — orient every pair $\{x,y\}$ independently and uniformly at random — with a triple $\{x,y,z\}$ declared a hyperedge iff the tournament restricted to it is a directed 3-cycle (cyclically oriented) rather than transitive. Exactly $2$ of the $8$ possible orientations of a 3-vertex tournament are cyclic, giving edge-density exactly $1/4$ in every large subset (this is a "palette"-type / quasirandom construction, later shown by arXiv:2408.09643 to be an instance of a fully general family of such constructions). This construction is $K_4^{(3)-}$-free-in-the-relevant-sense because a broken tetrahedron on 4 vertices would force an inconsistency in the cyclic-triangle pattern across the $4$ triples of a tournament on 4 vertices — establishing $\pi_u(K_4^{(3)-}) \ge 1/4$. - Follow-on work extending past this base case: August Y. Chen, Bjarne Schülke, "Beyond the broken tetrahedron," arXiv:2211.12747 (*Combin. Probab. Comput.*) — resolves the uniform Turán density of the 5-vertex 3-graph obtained by adding to $K_4^{(3)-}$ one more vertex whose link is a matching, as a stepping stone toward the still-open uniform Turán density of the full tetrahedron $K_4^{(3)}$. - "Palettes determine uniform Turán density" (arXiv:2408.09643) proves that palette-type constructions (of which the random-tournament/cyclic-triangle construction above is the founding example) always give the tight lower bound for uniform Turán density, in general — turning the ad hoc lower-bound trick used for $K_4^{(3)-}$ into a universal principle and removing the need for case-specific regularity-method lower-bound arguments. - Related known values in the same research program (for context on how rare exact answers are): Reiher–Rödl–Schacht separately characterized $\pi_u(F)=0$ and showed there is no 3-graph $F$ with $\pi_u(F)\in(0,1/27)$ — i.e. uniform Turán density "jumps" from $0$ to $\ge 1/27$ — and other papers have since pinned down further exact values (e.g. $8/27$, arXiv:2407.05829).

Solution

Answer: $\pi_u(K_4^{(3)-}) = 1/4$.

The transferable technique — two routes to the same wall, and why both matter

1. Flag algebras (Glebov–Král'–Volec, 2013/2016). Encode the extremal problem as a semidefinite-programming feasibility question over "flag" densities (Razborov's framework): express the density-increment obstruction to avoiding $K_4^{(3)-}$ in uniformly-dense hypergraphs as a sum-of-squares certificate that a computer solver can find and verify. This is a fully mechanical, computer-assisted route — it does not require inventing a bespoke combinatorial argument for this specific hypergraph, only setting up the right flag-algebra optimization and running the solver. Its transferable value is as a *discovery engine*: flag algebras can numerically locate the right constant (here $1/4$) and often a certificate-shaped proof, before anyone has a human-readable argument — exactly the role it played here, being first to land the exact value. 2. Hypergraph regularity method (Reiher–Rödl–Schacht, 2016/2018). Re-derive the same bound using the regularity/counting-lemma machinery for 3-uniform hypergraphs (Gowers; Nagle–Rödl–Schacht; Rödl–Skokan) applied to the specific notion of weak quasirandomness relevant here: a hypergraph is weakly $(d,\eta)$-quasirandom if every vertex subset $U$ spans $d\binom{|U|}{3}\pm\eta|V|^3$ edges. The proof shows that once a large hypergraph is weakly $(1/4+\varepsilon,\eta)$-quasirandom for small enough $\eta$, a regularity decomposition of the underlying "reduced hypergraph" is forced to contain a configuration that blows up into a copy of $K_4^{(3)-}$. This route is *not* computer-assisted, generalizes more readily (it directly produced the follow-up "no $F$ with $\pi_u(F)\in(0,1/27)$" jump theorem and an ordered variant of the $K_4^{(3)-}$ result), and became the template other uniform-Turán-density papers build on. 3. The matching lower-bound construction — the truly reusable idea. Both upper-bound proofs are matched by the *same* elegant extremal construction: put a random tournament on the vertex set and take hyperedges to be the cyclically-oriented triples. This single random object simultaneously (a) is uniformly quasirandom at density exactly $1/4$ in every large vertex subset (because $1/4$ of all triples in a random tournament are cyclic, independent of which subset you look at — this is what makes it a valid *uniform*-density lower-bound witness, not just an ordinary Turán-density one), and (b) avoids $K_4^{(3)-}$-type configurations by a local combinatorial constraint on tournament sub-orientations. This "encode density asymmetry via a random linear/cyclic order, then read off hyperedges from local order-patterns" idea — later formalized as the general palette construction (Rödl, 1980s; proven universally tight by arXiv:2408.09643) — is exactly the transferable move: *any* open uniform-Turán-density problem's lower bound is now known to reduce to searching over palette-type order/coloring constructions, rather than inventing a bespoke gadget each time.

Why this matters for open problems that depend on it: $K_4^{(3)-}$ was, for ~30 years, the only 3-graph with a known exact uniform Turán density. It is now the base case and proof-template for the whole research program: the palette-construction lower-bound recipe and the regularity-method upper-bound recipe demonstrated here are the two tools every subsequent uniform-Turán-density result (the 8/27 case, the "beyond the broken tetrahedron" 5-vertex case, the large-stars case, the tight-cycles case, etc.) directly reuses. The full tetrahedron $K_4^{(3)}$ itself — the natural next target — remains open.

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 — supplies the regularity/counting-lemma machinery underlying the Reiher–Rödl–Schacht proof route. - Turán number ex(n,H): extremal edge-count for forbidden subgraphs — the classical (non-uniform) Turán-density notion this result strengthens/refines. - Open natural successor: the uniform Turán density of the full tetrahedron $K_4^{(3)}$ is still unknown — the problem this base case was expected to be a stepping stone toward (per arXiv:2211.12747, "Beyond the broken tetrahedron"). - arXiv:2408.09643 ("Palettes determine uniform Turán density") — promotes this page's ad hoc lower-bound construction into a general theorem, i.e. formalizes exactly the "transferable idea" flagged above. - arXiv:2407.05829 (uniform Turán density $=8/27$) and arXiv:2409.03699 (large stars) — later exact-value results in the same program, using the same two-pronged (palette lower bound + regularity or flag-algebra upper bound) template.