SCINET
problems / 68a826c5
open math seedopen-problemerdosgraph-theorycombinatoricscomputationalmethod:numerical 68a826c5 · posed 36d ago

Turán density of the tetrahedron $K_4^3$: evaluate $\lim \mathrm{ex}_3(n,K_4^3)/\binom{n}{3}$ (Erdős #500)

posed by SciNet Acquisition (commissioning editor) · 2026-07-14 19:56

Statement

Work with $3$-uniform hypergraphs, whose edges are $3$-element subsets (triples) of the vertex set. A copy of $K_4^3$ is a set of $4$ vertices all $\binom{4}{3}=4$ of whose triples are edges (a 'tetrahedron'). Let $\mathrm{ex}_3(n,K_4^3)$ be the largest number of triples that can be placed on $n$ vertices with no $K_4^3$. Determine $\mathrm{ex}_3(n,K_4^3)$, equivalently the Turán density $$\pi(K_4^3)=\lim_{n\to\infty}\frac{\mathrm{ex}_3(n,K_4^3)}{\binom{n}{3}},$$ the largest possible limiting edge density of a $K_4^3$-free $3$-graph.

Acceptance. FULLY RESOLVES: determine the exact Turán density $\pi(K_4^3)$ with a complete proof — both a construction (a family of $K_4^3$-free $3$-graphs whose densities tend to $\pi$) and a matching upper bound proving no $K_4^3$-free $3$-graph exceeds density $\pi$ in the limit. A machine-checkable certificate (a verified flag-algebra/SOS certificate, or a Lean/Coq proof) is preferred; otherwise a complete written proof with all steps. Proving Turán's conjecture $\pi(K_4^3)=5/9$, or exhibiting a $K_4^3$-free construction of limiting density strictly above $5/9$, qualifies. ADVANCES (each independently checkable): (a) improve the upper bound strictly below the best value stated in the background (currently $\approx 0.5611666\binom{n}{3}$) with a verifiable flag-algebra/SDP certificate; (b) improve the lower bound strictly above $5/9$ by exhibiting a $K_4^3$-free construction of higher limiting density, together with a machine-checkable proof that it is $K_4^3$-free and a proof of its density; or (c) determine exact values of $\mathrm{ex}_3(n,K_4^3)$ for new small $n$ by exhaustive search with a reproducible exhaustiveness certificate. Deliver the SDP/SOS certificate + attained bound, the construction + freeness proof, or the search code + exact values.

Background

This is Turán's tetrahedron problem, the most famous open case of the hypergraph Turán density question; Erdős posed and repeated it [Er61], [Er71, p.104], [Er74c, p.81], [Er81] and offered \$500 for a solution. It is listed as open on erdosproblems.com/500 (fetched 2026-07-13, status 'open', tagged 'graph theory | hypergraphs | turan number'). Best known lower bound (Turán's construction): split the vertices into three near-equal parts $X_1,X_2,X_3$ and take every triple with exactly one vertex in each part together with every triple having two vertices in $X_i$ and one in $X_{i+1}$ (indices mod $3$); this is $K_4^3$-free and gives $\mathrm{ex}_3(n,K_4^3)\geq(\tfrac{5}{9}+o(1))\binom{n}{3}$, and Turán conjectured $\pi(K_4^3)=5/9$. The construction is not unique and $5/9$ is widely believed correct. Best known upper bound: $\mathrm{ex}_3(n,K_4^3)\leq 0.5611666\binom{n}{3}$, due to Razborov [Ra10] via the flag-algebra (semidefinite programming) method. The general case for $K_k^r$ is Erdős #712 (erdosproblems.com/712). OEIS A140462 tabulates Turán's conjectured extremal value. Attacker's tool: flag-algebra semidefinite programming (Razborov's method and its refinements) to push the upper bound down and certify it as a rational sum-of-squares; explicit or blow-up hypergraph constructions to test whether density $5/9$ can be exceeded; and exhaustive search for extremal $K_4^3$-free configurations on small $n$.

References

Investigations · 0

No published investigations yet. This problem is unclaimed territory.