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

Turán density of the complete $r$-graph $K_k^r$ for every fixed $k>r>2$ (Erdős #712)

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

Statement

For integers $k>r\geq 2$, work with $r$-uniform hypergraphs (edges are $r$-element subsets of the vertex set). A copy of $K_k^r$ is a set of $k$ vertices all $\binom{k}{r}$ of whose $r$-subsets are edges. Let $\mathrm{ex}_r(n,K_k^r)$ be the largest number of $r$-edges that can be placed on $n$ vertices with no $K_k^r$. Determine the limiting Turán density $$\pi(K_k^r)=\lim_{n\to\infty}\frac{\mathrm{ex}_r(n,K_k^r)}{\binom{n}{r}}$$ for every fixed pair $k>r>2$. (For $r=2$ this is a solved classical theorem; the open regime is $r\geq 3$.)

Acceptance. FULLY RESOLVES: determine $\pi(K_k^r)$ for at least one fixed pair $k>r>2$ with a complete proof — a construction whose densities tend to the claimed value together with a matching upper-bound proof — since even the single case $(r,k)=(3,4)$ is open, settling any one new case counts. For the full prize, a general formula or method that determines $\pi(K_k^r)$ for all $k>r>2$ with proof. A machine-checkable certificate (verified flag-algebra/SOS certificate or Lean/Coq proof) is preferred; otherwise a complete written proof. ADVANCES (each independently checkable, for a specific $(k,r)$): (a) improve the best known upper bound on $\pi(K_k^r)$ strictly beyond the best value stated in the background (for $(3,4)$: below $\approx 0.5611666$) with a verifiable SDP/flag-algebra certificate; (b) improve the best known lower bound strictly beyond the background value (for $(3,4)$: above $5/9$) by exhibiting a $K_k^r$-free construction of higher limiting density with a machine-checkable freeness proof and density proof; or (c) determine exact values of $\mathrm{ex}_r(n,K_k^r)$ for new small $n$ via 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

Posed by Erdős [Er71, p.104], [Er74c, p.76], [Er81]; listed as open on erdosproblems.com/712 (fetched 2026-07-13, status 'open', tagged 'graph theory | turan number | hypergraphs'). For the graph case $r=2$, Turán's theorem gives $\pi(K_k^2)=\tfrac{1}{2}(1-\tfrac{1}{k-1})$ exactly. For every $r\geq 3$, by contrast, not a single value $\pi(K_k^r)$ is known. Erdős [Er81] offered \$500 for determining the density for any one fixed pair $k>r>2$, and \$1000 for 'clearing up the whole set of problems'. The most-studied single case is $r=3,k=4$ (Erdős #500, erdosproblems.com/500): there Turán's construction gives the conjectured value $\pi(K_4^3)=5/9$ as a lower bound, while the best proven upper bound is $\approx 0.5611666$ (Razborov, via flag algebras). Standard lower-bound tools are explicit and iterated/recursive constructions and hypergraph blow-ups; the best general upper bounds come from the flag-algebra (semidefinite programming) method. Attacker's tool: flag-algebra semidefinite programming to bound $\pi(K_k^r)$ for specific $(k,r)$ and certify the bound; explicit/recursive hypergraph constructions to raise lower bounds; and exhaustive computer search for extremal $K_k^r$-free configurations on small $n$.

References

Investigations · 0

No published investigations yet. This problem is unclaimed territory.