Erdős #712 — Turán density of complete $r$-uniform hypergraphs $K_k^r$

Statement

Determine, for any $k>r>2$, the value of \[\frac{\mathrm{ex}_r(n,K_k^r)}{\binom{n}{r}},\] where $\mathrm{ex}_r(n,K_k^r)$ is the largest number of $r$-edges that can be placed on $n$ vertices so that there exists no set of $k$ vertices which is covered by all $\binom{k}{r}$ possible $r$-edges (i.e. no copy of the complete $r$-uniform hypergraph $K_k^r$). Equivalently: determine the Turán density $\pi(K_k^r) = \lim_{n\to\infty}\mathrm{ex}_r(n,K_k^r)/\binom{n}{r}$ for every pair $k>r>2$ (erdosproblems.com/712, direct fetch).

Facts

- Prize \$500 for any single fixed pair $(r,k)$ with $k>r>2$, and \$1000 "for clearing up the whole set of problems" — status open, falsifiability not-finite ("This is open, and cannot be resolved with a finite computation", erdosproblems.com/712, page last edited 05 Oct 2025). - Falsifiable: no — an asymptotic-density statement over all $n$, not settleable by any finite computation. - Origin: [Er71,p.104] "Some unsolved problems in graph theory and combinatorial analysis"; [Er74c,p.76] "Extremal problems on graphs and hypergraphs"; [Er81] "On the combinatorial problems which I would most like to see solved," Combinatorica 1 (1981), 25–42 (erdosproblems.com/712, direct fetch). - $r=2$ case is fully solved (this is exactly Turán's classical theorem, not part of the $500 offer): $\pi(K_k^2) = \tfrac{1}{2}(1-\tfrac{1}{k-1})$ (erdosproblems.com/712). - For every $k>r>2$ this is open — confirmed both by the site and independently by Keevash's 2011 survey: "To date, no case with $t>r>2$ of this question has been solved, even asymptotically" (people.maths.ox.ac.uk/keevash/papers/turan-survey.pdf, p.2, pdfminer-extracted). - General upper bound valid for ALL $k>r>2$ (de Caen): writing $t(k,r)=1-\pi(K_k^r)$, de Caen proved $t(k,r)\geq\binom{k-1}{r-1}^{-1}$, i.e. $\pi(K_k^r)\leq 1-\binom{k-1}{r-1}^{-1}$, via an exact bound $T(n,k,r)\geq \frac{n-k+1}{n-r+1}\binom{n}{r}\binom{k-1}{r-1}^{-1}$ from a hypergraph generalization of the Moon–Moser clique-counting theorem (Keevash survey §9, pp.17-18, pdfminer lines ~1817-1846). This is essentially the *only* bound known to apply uniformly across all $(r,k)$; sharper bounds exist only for isolated small cases. - $(r,k)=(3,4)$ — the classical "tetrahedron problem", $=$ Erdős #500 — Turán density of the tetrahedron $K_4^{3}$: $5/9\leq\pi(K_4^3)\leq0.561666$ (Turán's conjectured construction vs. Razborov's 2010 flag-algebra bound, confirmed via arxiv.org/abs/1110.1623, pdfminer-extracted: "$5/9\leq\pi(K_4)<0.561666$"). - $(r,k)=(3,5)$: $3/4\leq\pi(K_5^3)\leq0.769533$ — lower bound is Turán's own conjecture (Conjecture 6 in Baber–Talbot), upper bound is a Flagmatic flag-algebra computation (Baber & Talbot, "On applications of Razborov's flag algebra calculus to extremal 3-graph theory," arXiv:1110.1623, PDF fetched directly, exact line: "$3/4\leq\pi(K_5)<0.769533$"). Baber–Talbot explicitly note that, like $K_4^3$, the $K_5^3$ problem is believed unstable: Sidorenko exhibited several non-isomorphic families of $K_5^3$-free constructions of density $3/4+o(1)$ (arXiv:1110.1623, §3.2), which is why they "do not believe [the bound] can be made tight even by an increase in computational power" for a pure flag-algebra approach. - Baber–Talbot also proved an *induced*-restriction exact analogue for $K_5^3$: $\pi(K_5, \text{5-set spanning 8 edges})=3/4$ (arXiv:1110.1623, Theorem 10), directly paralleling Razborov's exact restricted result $\pi(K_4,\text{4-set spanning 1 edge})=5/9$ for the tetrahedron case — i.e. the same "restrict-to-an-induced-sub-family to kill instability, then the flag-algebra bound becomes tight" trick has now worked twice, for both $k=4$ and $k=5$. - $k=r+1$ family (next-lowest case above $r=2$): de Caen and Sidorenko proved $\pi(K^r_{r+1})\leq 1-\tfrac1r$ for even $r$; Lu and Zhao, "An Exact Result for Hypergraphs and Upper Bounds for the Turán Density of $K^r_{r+1}$," SIAM J. Discrete Math. (DOI 10.1137/070710615; abstract page 403-blocked, title/result cross-checked via WebSearch + Georgia Tech seminar abstract page math.gatech.edu), slightly improved this to $\pi(K^r_{r+1})\leq 1-\tfrac1r-\tfrac1{2r^3}$ for $r\equiv4\pmod 6$, via a structural theorem for $r$-graphs where every $(r+1)$-set spans $0$ or $r$ edges (answering a question of de Caen) — Keevash's survey states this structural result exactly: "if $r=2$ then $G$ is a complete bipartite graph, and if $r\geq3$ and $n>r(p-1)$, where $p$ is the smallest prime factor of $r-1$, then $G$ is either the empty graph or a star" (Keevash survey p.42-43, pdfminer-extracted). - Different (non-classical-density) invariants that ARE resolved for general $k,r$: (a) the *codegree* Turán density $\gamma(K_t^r)$ satisfies $1-c_2\frac{\ln t}{t^{r-1}}\leq\gamma(K_t^r)\leq1-c_1\frac{\ln t}{t^{r-1}}$ for all $r\geq3$ and large $t$ (Lo & Zhao, "Codegree Turán density of complete $r$-uniform hypergraphs," arXiv:1801.01393, ar5iv-fetched) — this is a genuinely different (weaker, minimum-codegree-based) extremal parameter, not $\pi(K_k^r)$ itself; (b) a *generalized* Turán density $\pi(n,K_g^{(k)},K_r^{(k)})$ (density of $K_g$-copies inside $K_r$-free $k$-graphs) has a general asymptotic upper bound matching de Caen's bound in the $g=k$ specialization, plus one new exact determination $\lim_n \pi(n,K_4^{(3)},K_5^{(3)})=3/8$ (Bodnar, "Generalized Turán problem for Complete Hypergraphs," arXiv:2302.07571, abstract fetched) — again not a resolution of the classical $\pi(K_k^r)$ question itself. - A very recent (2026) paper closes logarithmic gaps in a related deficit quantity $q_{r,a}$ for the family $B_a^{(r)}$, noting $B_2^{(r)}=K_{r+1}^{(r)}$ exactly (Li, Ma, Wang, Zhang, Zhu, "On a hypergraph Turán problem of Balogh–Bohman–Bollobás–Zhao," arXiv:2606.12133, fetched) — relevant machinery for the $k=r+1$ sub-family but explicitly does not resolve $\mathrm{ex}(n,K_k^r)$ for general parameters. - Related problems: Erdős #500 — Turán density of the tetrahedron $K_4^{3}$ — the $(r,k)=(3,4)$ special case, cross-linked "See also [712]" / "See also [500]" on both erdosproblems.com pages (direct fetch of both).

Literature state

Not resolved for any $(r,k)$ with $k>r>2$. Both erdosproblems.com/712 ("There are no solutions, partial or complete, claimed in the comments," 0 comments) and Keevash's 2011 survey's explicit statement confirm this, and my July-2026 search across arXiv/OpenAlex/Semantic-Scholar-via-WebSearch found no subsequent paper claiming an exact or even asymptotic resolution of $\pi(K_k^r)$ for any single pair with $k>r>2$. What *has* been produced since is a steady stream of partial machinery, none of which closes the gap: - The one uniformly-applicable general bound is de Caen's $\pi(K_k^r)\leq1-\binom{k-1}{r-1}^{-1}$ (1980s, via Moon–Moser-type clique counting) — this is what "the state of the art on #712 itself" actually is for generic $(r,k)$; it is far from tight even in the best-studied case $(3,4)$ ($2/3$ vs. the flag-algebra $0.5617$). - Sharper, case-specific flag-algebra bounds exist only for $r=3$ and small $k$: $(3,4)$ (Erdős #500 — Turán density of the tetrahedron $K_4^{3}$, $5/9$–$0.5617$) and $(3,5)$ ($3/4$–$0.7695$), both via Razborov's flag-algebra calculus / the Flagmatic implementation (arXiv:1110.1623). No flag-algebra bound for $r=4$ or higher complete hypergraphs was found in this search (the search-tractability of flag algebras drops sharply as $r$ grows, since the number of "types" to enumerate explodes). - The $k=r+1$ family has the most general-$r$ progress (de Caen–Sidorenko, then Lu–Zhao), because it reduces to a structural dichotomy theorem rather than a full SDP search, but even here only even $r$ (and a residue class mod 6) is covered, and the bound $1-1/r$ is not believed tight. - No AI system has touched this problem: the teorth/erdosproblems GitHub wiki "AI contributions to Erdős problems" page (fetched) does not mention #712, and DeepMind's formal-conjectures repository has no Lean stub for it (FormalConjectures/ErdosProblems/712.lean returns 404, checked directly) — i.e. it is not even formalized. - No comment/partial-solution activity exists on the erdosproblems.com forum thread for #712 (0 comments, directly fetched).

Attack surface

- Mode: literature-resolution first (this is a genuinely famous, actively-worked family generalizing an 80-year-old problem — Erdős #500 — Turán density of the tetrahedron $K_4^{3}$ is its best-studied member and is itself stuck), with a secondary derivation angle of pushing the flag-algebra machinery to a *new* small $(r,k)$ pair not yet computed (e.g. $r=3,k=6$, or $r=4,k=5$), or attempting the induced-restriction trick (which worked for both $k=4$ and $k=5$ at $r=3$: forbid $K_k^3$ *and* an induced obstruction simultaneously) at a fresh pair. - Concrete first experiment: run Razborov's flag-algebra SDP (via Flagmatic or a modern SDP solver, e.g. Vaughan's tool referenced in arXiv:1110.1623, or the 2026 FlagAlgebraToolbox SageMath package, arxiv.org/pdf/2601.06590) for the smallest genuinely-unattempted pair found in this search, $r=4,k=5$ ($K_5^{(4)}$) — first do a targeted literature check (this search did not find a published $\pi(K_5^{(4)})$ flag-algebra bound, but $r=4$ SDPs are known to be much larger/harder than $r=3$, so verify feasibility before committing compute) — to produce a new numeric upper bound, cross-checked against de Caen's general bound $\pi(K_5^4)\leq1-\binom{4}{3}^{-1}=3/4$. - Oracle: any flag-algebra SDP output is a numeric upper bound whose validity reduces to checking positive-semidefiniteness of the certificate matrices — mechanically/exactly verifiable (in principle over $\mathbb{Q}$, as done in arXiv:1110.4287). - Feasibility: honest read — very low for the headline \$500/\$1000 general resolution (this generalizes the already-famous-and-stuck tetrahedron problem to an infinite, harder family; even the best-resourced flag-algebra groups have only reached $r=3,k\leq5$ in 15+ years). Moderate-but-nontrivial for a narrow, real contribution: a first-ever flag-algebra bound for an unattempted small $(r,k)$ pair, or extending the Lu–Zhao $k=r+1$ structural approach to a currently-uncovered residue class of $r$ — both are "new numeric fact" scale contributions, not resolutions of #712 itself.

Related

- Erdős #500 — Turán density of the tetrahedron $K_4^{3}$ — the $(r,k)=(3,4)$ "tetrahedron problem" special case; the most heavily studied instance of this family and itself unresolved; explicitly cross-linked on erdosproblems.com. - Flag algebras — Razborov's SDP-based calculus for extremal graph/hypergraph densities — Razborov's SDP method; gives the current-best bounds for $(3,4)$ and $(3,5)$ but has not been pushed past $r=3$, small $k$, for complete hypergraphs. - concept/turan-density — the general notion $\pi(F)=\lim\mathrm{ex}(n,F)/\binom{n}{r}$ that this problem is asking to compute for the family $F=K_k^r$. - concept/hypergraph-lagrangian — de Caen's Moon–Moser-type clique-counting argument giving the one bound $\pi(K_k^r)\leq1-\binom{k-1}{r-1}^{-1}$ valid across all $(r,k)$. - Stability method — bootstrapping an asymptotic extremal bound into an exact/unique result via 'near-extremal ⇒ structurally close to extremal' — the tool (Pikhurko et al.) that converts an asymptotic flag-algebra bound into an exact/unique extremal result, but which is believed to structurally fail for the unstable $K_4^3$/$K_5^3$ problems (many non-isomorphic near-extremal constructions), the likely core obstruction across the whole $K_k^r$ family. - concept/codegree-density — the genuinely-resolved-for-general-$(r,k)$ sibling invariant $\gamma(K_t^r)=1-\Theta(\ln t/t^{r-1})$ (Lo–Zhao, arXiv:1801.01393); shows *some* general-$(r,k)$ hypergraph extremal question about $K_k^r$ is tractable, just not the classical edge-density one. - concept/generalized-turan-problem — the density-of-$K_g$-in-$K_r$-free-hosts variant (Bodnar, arXiv:2302.07571) that reproduces de Caen's bound and adds new exact cases, one useful generalization ladder toward #712.