Erdős #500 — Turán density of the tetrahedron $K_4^{3}$

Statement

What is $\mathrm{ex}_3(n,K_4^3)$, the largest number of $3$-edges (triples) that can be placed on $n$ vertices so that no $4$-set of vertices is covered by all $\binom{4}{3}=4$ possible triples (i.e. the 3-uniform hypergraph contains no "tetrahedron" $K_4^{(3)}$)? Equivalently, determine the Turán density $\pi(K_4^{(3)}) = \lim_{n\to\infty} \mathrm{ex}_3(n,K_4^3)/\binom{n}{3}$. This is the classical Turán's tetrahedron problem, restated by Erdős as one of his favourite open problems (erdosproblems.com/500, direct fetch).

Facts

- Prize \$500; status open, falsifiability not-finite — the site explicitly states "This is open, and cannot be resolved with a finite computation" (erdosproblems.com/500, page last edited 05 Oct 2025, reflects site-owner T.F. Bloom's belief). - Falsifiable: no. Unlike a single combinatorial existence statement, this is an asymptotic-density question; no finite computation settles it (confirmed by the site's own flag). - Origin: [Er61] "Some unsolved problems" (Magyar Tud. Akad. Mat. Kutató Int. Közl., 1961, 221-254); [Er71,p.104] "Some unsolved problems in graph theory and combinatorial analysis" (Proc. Conf. Oxford 1969); [Er74c,p.81] "Extremal problems on graphs and hypergraphs" (1974, 75-84); [Er81] "On the combinatorial problems which I would most like to see solved" (Combinatorica 1 (1981), 25-42) — Erdős offered \$500 for this special case ($r=3,k=4$) and \$1000 for the general family, see Erdős #712 — Turán density of complete $r$-uniform hypergraphs $K_k^r$ (bib entries fetched directly from erdosproblems.com/bibs/{Er61,Er71,Er74c,Er81}). - Known results / best bounds: - Lower bound (Turán's construction, conjectured tight): split $n$ vertices into 3 equal parts $X_1,X_2,X_3$; take triples with one vertex in each part, or two vertices in $X_i$ and one in $X_{i+1}$ (indices mod 3). This gives $\mathrm{ex}_3(n,K_4^3) \geq (5/9+o(1))\binom{n}{3}$ (erdosproblems.com/500). Turán believed $5/9$ is the truth. - Upper bound history (Keevash survey, people.maths.ox.ac.uk/keevash/papers/turan-survey.pdf, pp.17-18, pdfminer-extracted text lines ~1470-1482): de Caen gave an early bound via a double-counting argument [de Caen 1983]; Chung–Lu [CL99] improved it to $0.593592\ldots$; Razborov (2010), using flag algebras, announced (and Baber–Talbot [BT11] "Hypergraphs do jump" independently verified) the current record $\pi(K_4^{(3)}) \leq 0.5611666$ — cited on erdosproblems.com/500 as "[Ra10]" and confirmed as still the current best bound as of the site's Oct-2025 edit and my July-2026 search (no improvement found in the 2011-2026 literature). - No stability — the core obstruction: unlike most Turán-type problems, the tetrahedron problem has exponentially many pairwise non-isomorphic constructions achieving the conjectured extremal density $5/9$ (Brown; Kostochka; Fon-der-Flaass; Frohmader — all cited in Keevash's survey, p.19). This absence of stability is believed to be why flag-algebra/SDP methods, despite closing many other hypergraph Turán problems, have stalled on this one since 2010-2011. - A genuinely solved restricted sub-case: Razborov [Ra10] proved exactly $e(G) \leq (5/9+o(1))\binom{n}{3}$ for 3-graphs $G$ in which no 4-set spans exactly 1 or exactly 4 edges — an explicit, hand-verifiable flag computation. Pikhurko (2011, [154] in Keevash's survey) then applied the stability method to this restricted sub-problem to get an EXACT uniqueness result for large $n$: Turán's construction is the unique extremizer — but this only works because the restricted sub-problem (unlike the full tetrahedron problem) does have stability. - Kalai's algebraic generalization: Kalai [98] ("A new approach to Turán's conjecture," Graphs Combin. 1 (1985)) proposed a rank/exterior-algebra conjecture (via a matrix $M_s(G)$ built from indeterminates indexed by pairs and edges) generalizing the tetrahedron problem; itself still open (Keevash survey, §11). - Weaker combinatorial variant: Fon-der-Flaass [64] gave an independent construction (via oriented graphs with no induced oriented 4-cycle) also achieving density $5/9$; whether all such "Fon-der-Flaass-type" constructions have density $\geq 4/9$ was posed as a weakening, with partial progress by Razborov ("On the Fon-der-Flaass interpretation of extremal examples," [159]). - General undecidability caveat: Hatami & Norine (2011) proved that determining the validity of general flag-algebra/Cauchy-Schwarz-derived linear inequalities is undecidable (Keevash survey, p.19, citing [92]) — so there is no guarantee that flag algebras, even with unlimited computation, can ever close this specific gap. - Related generalization: the general problem $\mathrm{ex}_r(n,K_k^3)/\binom{n}{r}$ for all $k>r>2$, Erdős #712 — Turán density of complete $r$-uniform hypergraphs $K_k^r$ ($\$1000$ prize, "See also [500]"/"See also [712]" cross-link, both confirmed by direct fetch), is also fully open. - Related problems: Erdős #712 — Turán density of complete $r$-uniform hypergraphs $K_k^r$ — the general Turán($r,k$) problem this is the $r=3,k=4$ special case of.

Literature state

Not resolved. Both the primary source (erdosproblems.com/500, last edited 05 Oct 2025, "There are no solutions, partial or complete, claimed in the comments") and my independent July-2026 search confirm the gap between $5/9 \approx 0.5556$ (Turán's conjectured-tight lower bound) and $0.5611666$ (Razborov 2010 flag-algebra upper bound) has not been closed by any published result. No comment or partial-solution claim exists on erdosproblems.com/500 or erdosproblems.com/712 (both directly fetched). No DeepMind formal-conjectures Lean stub exists for either #500 or #712 — both FormalConjectures/ErdosProblems/500.lean and 712.lean return HTTP 404 on raw.githubusercontent.com (checked directly) — i.e. the problem has not even been formalized, let alone attempted by an AI theorem prover.

Genuine, verified partial progress exists only on weaker or differently-normed variants of the same extremal question, not on the classical density $\pi(K_4^{(3)})$ itself: - Broken tetrahedron $K_4^{(3)-}$ (tetrahedron minus one edge): its *uniform* Turán density (a refinement w.r.t. quasirandom/uniformly-dense host hypergraphs, motivated by an Erdős–Sós question) was determined exactly to be $1/4$, independently by Glebov, Král' and Volec (flag algebras) and by Reiher, Rödl and Schacht (hypergraph regularity / reduced-hypergraph method) — cross-checked via WebSearch against multiple secondary sources. This line is actively being extended: arxiv.org/abs/2211.12747 ("Beyond the broken tetrahedron," fetched) determines the uniform Turán density of the next 3-graph beyond $K_4^{(3)-}$, explicitly framed by the authors as "identifying intermediate problems on the path toward resolving the full $\pi_u(K_4^{(3)})$ conjecture." - $\ell_2$-norm variant fully solved: Balogh, Clemen and Lidický, "Solving Turán's Tetrahedron Problem for the $\ell_2$-Norm," arXiv:2108.10408 (J. Lond. Math. Soc. 2022), proved Turán's conjecture is TRUE asymptotically when hypergraph "density" is measured by the sum of squared codegrees ($\ell_2$-norm of the codegree vector) rather than raw edge count ($\ell_1$-norm). This was strengthened to an exact uniqueness result by Bodnár, Chen, Deng et al., "Tetrahedron Conjecture in the $\ell_2$-norm," arXiv:2511.12506 (Nov 2025, fetched) — proving the Turán 3-partite construction is the *unique* extremizer for large $n$ in this norm. - The restricted "no 4-set with exactly 1 or exactly 4 edges" sub-case is fully and exactly solved (Razborov's asymptotic flag computation + Pikhurko's stability-based exact/uniqueness result, per Keevash's survey pp.17-19).

None of these resolve the classical (edge-count / $\ell_1$-norm, unrestricted) tetrahedron problem itself, which remains the genuinely open $500 question.

Attack surface

- Mode: literature-resolution first (this is a 65-year-old, heavily-attacked problem; flag-algebra/SDP mining has stalled since 2010-2011 with no improvement found through 2026) with a secondary derivation angle via the actively-moving uniform-Turán-density / hypergraph-regularity research ladder, which is structurally closer to the classical problem than raw SDP recombination. - Concrete first experiment: this is explicitly NOT amenable to finite search (site flag: "cannot be resolved with a finite computation"). Two concrete, runnable directions instead: (1) low-expected-value recombination — rerun Razborov-style flag-algebra SDP computations (e.g. via Vaughan's flagmatic or a modern SDP solver) at higher complexity/more vertex-types than the 2010 computation, to test whether $<0.5611666$ is reachable — low expected value given 15 years of stall and the Hatami–Norine undecidability caveat; (2) higher-expected-value derivation — extend the "Beyond the broken tetrahedron" (arxiv.org/abs/2211.12747) uniform-Turán-density ladder to the next 3-graph closer to $K_4^{(3)}$ itself, since that program is explicitly active (2022→2025 papers) and not yet exhausted. - Oracle: any flag-algebra SDP output is a numeric upper bound whose validity is mechanically checkable by verifying positive-semidefiniteness of the certificate matrices — in principle exact/rational verification is possible (Keevash survey footnote: check all symmetric-minor determinants are positive via symmetric Gaussian elimination), though laborious by hand. - Feasibility: low for the headline \$500 problem itself. This is one of the most famous and hardest open problems in extremal hypergraph theory: 65+ years old, actively attacked with the strongest known tools (flag algebras have been stalled at this exact bound since 2010-2011), provably lacking stability (so the standard toolkit that solves "nice" Turán problems is structurally blocked here), and subject to a general undecidability barrier (Hatami–Norine) for the class of inequalities flag algebras can even in principle certify. A realistic near-term contribution is on a weaker sibling — the uniform-Turán-density ladder, the $\ell_2$-norm variant, or the general Erdős #712 — Turán density of complete $r$-uniform hypergraphs $K_k^r$ framing — rather than the classical density itself.

Related

- Erdős #712 — Turán density of complete $r$-uniform hypergraphs $K_k^r$ — the general Turán($r,k$) problem (\$1000 prize) that #500 is the $r=3,k=4$ special case of; explicitly cross-linked ("See also [500]" / "See also [712]") on both erdosproblems.com pages (direct fetch). - Flag algebras — Razborov's SDP-based calculus for extremal graph/hypergraph densities — Razborov's method (2007, J. Symbolic Logic) that gives the current-best $0.5611666$ upper bound [Ra10] and fully solves both the broken-tetrahedron uniform-density problem and (jointly with regularity methods) related restricted sub-cases. - 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 — the Reiher–Rödl–Schacht "reduced hypergraph" technique that independently re-solved the broken tetrahedron and drives the uniform-Turán-density research ladder ("Beyond the broken tetrahedron," arxiv.org/abs/2211.12747). - Uniform Turán density π_u(F) — Turán problem refined to uniformly-dense (quasirandom) host hypergraphs (Erdős–Sós, ~1990) — the Erdős–Sós-motivated refinement of ordinary Turán density (over quasirandom/uniformly-dense host hypergraphs) under which $K_4^{(3)-}$ is fully solved ($=1/4$) while $K_4^{(3)}$ itself remains open; the most promising active derivation ladder toward this problem. - Stability method — bootstrapping an asymptotic extremal bound into an exact/unique result via 'near-extremal ⇒ structurally close to extremal' — Pikhurko's tool giving an exact/unique result on the restricted "no 4-set with 1 or 4 edges" sub-case; the full tetrahedron problem is believed to structurally lack stability (exponentially many extremal constructions), the likely reason it has resisted 65 years of attack. - concept/algebraic-shifting — Kalai's exterior-algebra/rank approach (Graphs Combin. 1 (1985)) generalizing Turán's tetrahedron conjecture via a matrix-rank inequality; itself unresolved. - ℓp-norm (codegree-power-sum) reformulation of Turán density: maximize Σ(codegree)^p instead of edge count — the $\ell_2$-norm (codegree-squared-sum) reformulation of Turán-type extremal problems, under which the tetrahedron conjecture IS solved asymptotically (arxiv.org/abs/2108.10408, 2022) with uniqueness pinned down (arxiv.org/abs/2511.12506, 2025).