Erdoes #712 - working report - Erdős Problem a Day

Erdős problem #712 — wave w010

Date: 2026-07-28 (UTC)

Claim labels used below:

(a) elementary-rigorous: proved from definitions in this report.
(b) rigorous-modulo-named-theorem/source: the precise external source is named.
(c) plausible/structural-unverified: not asserted as a theorem.
(d) computational-only: established by the reproducible finite computation, not used as an unproved uniform statement.

0. Mandatory live-page gate

(a, direct page observation.) I fetched the rendered live page and its LaTeX-source view through the Bright Data browser path on 2026-07-28:

The live page says OPEN - $500. It has 0 comments on this problem, 0 claimed proofs for this problem, Interested in collaborating: None, and Currently working on this problem: None. The remaining activity-marker rows also say None. It says that the page was last edited on 05 October 2025. Thus neither mandatory stop condition (claimed proof/solution nor current worker) applied.

The page labels the problem #712: [Er71,p.104][Er74c,p.76][Er81] and gives the following exact statement (including the missing word in “can placed”):

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 which can placed on $n$ vertices so that there exists no set of $k$ vertices which is covered by all $\binom{k}{r}$ possible $r$-edges.

The only listed mathematical result is that Turán determined the graph case. The page also says that Erdős offered $500 for any one fixed pair $k>r>2$, $1000 for the whole family, and refers to problem #500 for $r=3,k=4$. There are no comments or claimed arguments to assess.

1. Statement/normalisation audit

(a). The displayed expression depends on $n$, while the following sentence on the page calls it “this limit”. The intended standard object is therefore

\pi(K_k^r):=\lim_{n\to\infty} \frac{\operatorname{ex}_r(n,K_k^r)}{\binom nr}.

The limit exists without any deep theorem. If $d_n=\operatorname{ex}_r(n,F)/\binom nr$, the average density of the induced $(n-1)$-vertex subgraphs of an $n$-vertex $F$-free $r$-graph is its own density. One induced subgraph has density at least that average, so $d_n\le d_{n-1}$. The bounded decreasing sequence $(d_n)$ has a limit.

(a). There is a factor-of-two inconsistency on the live page. With the displayed denominator $\binom n2$, Turán's graph theorem gives

\lim_n\frac{\operatorname{ex}_2(n,K_k^2)}{\binom n2} =1-\frac1{k-1},

not the page's $\frac12(1-\frac1{k-1})$. The latter is the normalisation by $n^2$. All finite results below concern the integer $\operatorname{ex}_r(n,K_k^r)$, so they are unaffected by this editorial normalisation issue.

2. Primary-source check and current state

(b). I verified all three old citation keys against primary scans:

Erdős, “Some Unsolved Problems in Graph Theory and Combinatorial Analysis” (1971), pp. 97–109. Page 104 defines the complete-hypergraph problem, says the relevant limit exists, and says its value is unknown for uniformity greater than two.
Erdős, “Extremal problems on graphs and hypergraphs” (1974), pp. 75–84, also indexed by DOI 10.1007/BFb0066181. Page 76 again says that the limit exists and is unknown for every $r>2,\ t>r$.
Erdős, “On the combinatorial problems which I would most like to see solved” (1981), pp. 25–42, DOI 10.1007/BF02579174. Section III.1 gives the $500-for-one-pair and $1000-for-all-pairs offers.

(b). The most recent directly relevant primary source I found is Liu–Schülke–Wang–Yang–Zhang, “Separating hypergraph Turán densities,” arXiv:2410.08921v2 (revised 9 February 2025). Its abstract explicitly says that $\pi(K_\ell^{(r)})$ remains unknown for every $\ell>r\ge3$. It proves the strict separation

\pi(K_\ell^{(r)})<\pi(K_{\ell+1}^{(r)}) \qquad(\ell>r\ge3),

but does not evaluate either side. This verifies that the problem was still completely open at the density-evaluation level in that source.

(b). Bodnár, “Generalized Turán problem for Complete Hypergraphs,” arXiv:2302.07571v2, likewise states that no complete $r$-graph density in this regime is known and identifies de Caen's theorem as the best general upper-bound framework. Its new exact $3/8$ result concerns a generalized density counting $K_4^3$'s inside $K_5^3$-free 3-graphs, not $\pi(K_5^3)$, so it does not solve #712.

(c, search-completeness qualification). Searches through 2026-07-28 found newer work on codegree, uniform, partite, Berge, and generalized Turán densities, but no primary source claiming an exact value of $\pi(K_k^r)$ for $k>r>2$. Absence from a literature search is not itself a theorem; the live status plus the explicit 2025 primary-source statement is the evidence for proceeding.

3. Exact reduction to covering designs

The following reduction is useful both conceptually and computationally.

Lemma 1 (a). Let $n\ge k>r$, put $s=n-k$, and let $H$ be an $r$-graph on $V$, $|V|=n$. Let

\mathcal D=\binom Vr\setminus E(H)

be its missing-edge $r$-graph. Then the following are equivalent:

$H$ is $K_k^r$-free.
Every $s$-set $S\subset V$ is disjoint from some $D\in\mathcal D$.
The transversal number satisfies $\tau(\mathcal D)>s$.
The $(n-r)$-sets $V\setminus D$, $D\in\mathcal D$, cover every $s$-set.

Proof. A $k$-set is $K=V\setminus S$ for a unique $s$-set $S$. It fails to span $K_k^r$ exactly when it contains a missing edge $D$, which is exactly $D\cap S=\varnothing$. This for every $S$ says that no $s$-set hits every member of $\mathcal D$. Complementing $D$ gives the last formulation. $\square$

Write $\operatorname{Cov}(v,b,t)$ for the minimum number of $b$-subsets of a $v$-set needed to cover all its $t$-subsets. Lemma 1 immediately gives the exact identity

\boxed{\quad \operatorname{ex}_r(n,K_k^r) =\binom nr-\operatorname{Cov}(n,n-r,n-k). \quad} \tag{1}

(a). This is an exact finite reduction, not a solution of the limiting problem. For fixed $k,r$ and $n\to\infty$, the covering target size $n-k$ and block size $n-r$ both grow with $n$, so (1) has not removed the uniform asymptotic difficulty.

4. Closed finite regimes from the reduction

4.1 One vertex beyond the forbidden clique

Theorem 2 (a). For every $k>r>2$,

\boxed{\quad \operatorname{ex}_r(k+1,K_k^r) =\binom{k+1}{r} -\left\lceil\frac{k+1}{k+1-r}\right\rceil . \quad} \tag{2}

Proof. Here $s=1$, so Lemma 1 asks for an $r$-set family with empty total intersection. Its complements are $(n-r)$-sets whose union is $V$. At least $\lceil n/(n-r)\rceil$ are needed by cardinality. Partition $V$ into that many pieces of size at most $n-r$, then enlarge each piece to size exactly $n-r$; this attains the bound. $\square$

4.2 General disjoint-missing-edge regime

Theorem 3 (a). Put $n=k+s$. If

n\ge(s+1)r,

then

\boxed{\quad \operatorname{ex}_r(n,K_k^r)=\binom nr-(s+1). \quad} \tag{3}

Moreover, $s+1$ missing edges are possible if and only if $n\ge(s+1)r$.

Proof. Any family of at most $s$ nonempty edges has a transversal of size at most $s$, obtained by choosing one point from each edge. Thus Lemma 1 requires at least $s+1$ missing edges. If $n\ge(s+1)r$, choose $s+1$ pairwise disjoint $r$-sets; every $s$-set misses at least one of them, so equality holds.

For necessity, if $s+1$ missing edges are not pairwise disjoint, one point hits two intersecting edges and one chosen point from each remaining edge produces a transversal of size at most $s$. Thus equality requires $s+1$ disjoint $r$-sets and hence at least $(s+1)r$ vertices. $\square$

4.3 A sharper complete answer when $n=k+2$ in two ranges

Theorem 4 (a). Let $n=k+2$ and $k>r>2$. Then

\operatorname{ex}_r(n,K_k^r)= \begin{cases} \binom nr-3,&n\ge3r,\\[2mm] \binom nr-4,&\left\lceil\frac{5r}{2}\right\rceil\le n<3r. \end{cases} \tag{4}

Proof. We need the minimum number of $r$-edges in a family $\mathcal D$ with $\tau(\mathcal D)\ge3$.

Three edges work exactly when they are pairwise disjoint, giving the first line by Theorem 3.

Now suppose $\mathcal D=\{D_1,D_2,D_3,D_4\}$ and $\tau(\mathcal D)\ge3$. No ground vertex lies in three $D_i$'s, since it and one point of the fourth edge would form a two-point transversal. Form the intersection graph $J$ on $\{1,2,3,4\}$, joining $i,j$ when $D_i\cap D_j\ne\varnothing$. Two disjoint edges in $J$ would supply two intersection points hitting all four $D_i$'s, so $J$ has matching number at most one. Such a graph is contained in either a star or a triangle.

In the star case, the three noncentral $D_i$'s are pairwise disjoint, so their union alone has size $3r$.
In the triangle case, the fourth $D_i$ is disjoint from the other three. No point is in all of those three, so incidence counting gives union size at least $\lceil3r/2\rceil$ for them, and at least $r+\lceil3r/2\rceil=\lceil5r/2\rceil$ overall.

Thus four edges require at least $\lceil5r/2\rceil$ vertices.

This threshold is attained. For $r=2q$, take disjoint sets $X_{12},X_{13},X_{23}$ of size $q$, set

D_1=X_{12}\cup X_{13},\quad D_2=X_{12}\cup X_{23},\quad D_3=X_{13}\cup X_{23},

and take a fourth $r$-set disjoint from their union. For $r=2q+1$, use sizes $q,q,q+1$ for $X_{12},X_{13},X_{23}$ and add one private point to $D_1$. In both cases the first three edges have transversal number two and union size $\lceil3r/2\rceil$; the disjoint fourth edge raises the transversal number to three. $\square$

For $r=3$, the two remaining small cases can also be settled.

Corollary 5 (a). For every $n\ge6$,

\boxed{ \operatorname{ex}_3(n,K_{n-2}^3)= \begin{cases} 14,&n=6,\\ 30,&n=7,\\ 52,&n=8,\\ \binom n3-3,&n\ge9. \end{cases}} \tag{5}

For $n=7$, five missing triples with transversal number three are, in one-based notation,

123,\quad167,\quad236,\quad456,\quad457.

Four cannot work on seven vertices by Theorem 4. For $n=6$, complementing the missing triples turns the condition into covering all 15 pairs with triples. Five triples would have to cover every pair exactly once, but the five pairs incident with any fixed vertex cannot be partitioned into two-pair contributions from triples through that vertex. Hence at least six missing triples are needed, and the cyclic construction in the verifier supplies six.

5. Exact fixed-pair table for $K_4^3$

5.1 Construction

(a). Partition the vertices cyclically into balanced parts $V_0,V_1,V_2$. Include:

every triple with one vertex in each part; and
every triple with two vertices in $V_i$ and one in $V_{i+1}$, indices modulo three.

This is $K_4^3$-free. If four vertices put at least three points in one part, the triple inside that part is missing. The remaining distributions are $2+2$ and $2+1+1$; in each, the cyclic rule omits at least one of the four triples.

For $n=3q,3q+1,3q+2$, direct counting gives respectively

\frac{q^2(5q-3)}2,\qquad \frac{q(5q^2+2q-1)}2,\qquad \frac{q(q+1)(5q+2)}2. \tag{6}

5.2 Matching lower bounds through $n=9$

Let

Q_n=\operatorname{Cov}(n,n-3,n-4).

Equation (1) says $\operatorname{ex}_3(n,K_4^3)=\binom n3-Q_n$.

(a).

$Q_4=1$.
$Q_5=3$, since 2-blocks must cover five points.
$Q_6=6$: five 3-blocks would have to cover all 15 pairs exactly once, and the fixed-vertex parity argument from Corollary 5 rules this out.
$Q_7=12$. Here is a self-contained proof of the only nontrivial base case.

Assume eleven 4-blocks cover all triples on seven points. Write $d_x$ and $d_{xy}$ for the numbers of blocks containing $x$ and $x,y$. The derived blocks through $x$ cover all pairs on the other six points, so $d_x\ge Q_6=6$. The blocks through $x,y$, with $x,y$ removed, cover all five remaining points by pairs, so $d_{xy}\ge3$.

Since

\sum_xd_x=44,\qquad \sum_{\{x,y\}}d_{xy}=66,

put $a_x=d_x-6$ and $b_{xy}=d_{xy}-3$. Then

\sum_xa_x=2,\quad \sum_{\{x,y\}}b_{xy}=3,\quad \sum_{y\ne x}b_{xy}=3a_x. \tag{7}

The excess $a_x=2$ at one point is impossible: (7) would demand incident $b$-weight six although the total $b$-weight is only three. Hence two points $x,y$ have $a=1$, all others have $a=0$, and (7) forces $b_{xy}=3$, with every other $b$ zero.

Let $W$ be the other five points. Six blocks contain $x,y$, and have form $xy\cup P$ for six distinct pairs $P\subset W$. There is one further $x$-block $x\cup A$, one further $y$-block $y\cup A'$, and three 4-blocks inside $W$. From $d_{xz}=d_{yz}=3$ for $z\in W$, the number of the six pairs $P$ containing $z$ shows $A=A'$.

The three internal $W$-blocks omit three distinct points; call their set $O$. For $u,v\in W$, the equality $d_{uv}=3$ becomes

\mathbf 1_{\{uv\text{ is one of the six }P\}} +2\mathbf 1_{\{u,v\subset A\}} =\mathbf 1_{\{u\in O\}}+\mathbf 1_{\{v\in O\}}. \tag{8}

Taking pairs inside the 3-set $A$ forces $A=O$. If $W\setminus A=\{p,q\}$, (8) then says $pq$ is not one of the six pairs $P$. Consequently no block containing $x$ contains the triple $xpq$, contradicting the assumed cover. Thus eleven blocks are impossible.

Finally, the elementary incidence recursion

\operatorname{Cov}(v,b,t)\ge \left\lceil\frac{v}{b}\operatorname{Cov}(v-1,b-1,t-1)\right\rceil \tag{9}

follows by applying the smaller covering problem to blocks through each point and summing point-block incidences. Therefore

Q_8\ge\left\lceil\frac85Q_7\right\rceil=20,\qquad Q_9\ge\left\lceil\frac96Q_8\right\rceil=30.

The construction in §5.1 has exactly $1,3,6,12,20,30$ missing triples for $n=4,\ldots,9$, so every bound is attained.

Exact table (a):

| $n$ | $\binom n3$ | minimum missing $Q_n$ | $\operatorname{ex}_3(n,K_4^3)$ | |---:|---:|---:|---:| | 4 | 4 | 1 | 3 | | 5 | 10 | 3 | 7 | | 6 | 20 | 6 | 14 | | 7 | 35 | 12 | 23 | | 8 | 56 | 20 | 36 | | 9 | 84 | 30 | 54 |

No novelty claim is made for these classical-size values; the contribution here is a complete short derivation plus an independent, dependency-free certificate.

6. Standalone re-verification

The complete checker is:

runs/erdos712_wavew010_verify.py

SHA-256 at completion:

3d73d69169f51e5edcb3719ea9e4e89e9859577440c01a7540782f457a702b23

Its mathematical verification uses only the Python standard library. It:

generates the cyclic construction rather than reading stored edge lists;
exhaustively checks every 4-set for $K_4^3$-freeness;
complements missing triples and checks the covering-design identity;
runs a from-scratch exact set-cover branch search proving that 5 blocks do not cover all pairs in $C(6,3,2)$ and that 11 blocks do not cover all triples in $C(7,4,3)$;
recomputes the incidence recursion and every table entry; and
checks representative instances of Theorems 2–4 and all exceptional witnesses in Corollary 5.

The exact branch is exhaustive because it selects an uncovered target and branches over every block containing it. Memoisation only discards a repeated covered-target mask reached with no fewer chosen blocks; its gain bound overestimates possible future coverage, so it cannot discard a genuine cover.

The optional source-audit mode downloads the exact five versioned primary PDFs cited in §2, verifies fixed SHA-256 digests, invokes the system pdftotext, and checks the specific “unknown” and prize phrases used in the report.

Run both independent audits:

python runs/erdos712_wavew010_verify.py
python runs/erdos712_wavew010_verify.py --check-sources

Observed clean output:

Exact ex_3(n,K_4^3) table:
  n=4: ex= 3, missing= 1, total= 4
  n=5: ex= 7, missing= 3, total=10
  n=6: ex=14, missing= 6, total=20
  n=7: ex=23, missing=12, total=35
  n=8: ex=36, missing=20, total=56
  n=9: ex=54, missing=30, total=84
Exhaustive no-cover search nodes: v=5: 1, v=6: 69, v=7: 30097
Near-diagonal constructions: verified on the stated test grids
ALL MATHEMATICAL CHECKS PASSED in 0.432 seconds

The source audit additionally ended with:

Primary-source audit:
  Er71: hash and 1 content phrase(s) verified
  Er74c: hash and 2 content phrase(s) verified
  Er81: hash and 2 content phrase(s) verified
  Bodnar23-v2: hash and 2 content phrase(s) verified
  Liu-et-al-24-v2: hash and 1 content phrase(s) verified
ALL SOURCE CHECKS PASSED in 9.124 seconds

(d). The exhaustive search is a second verification of the hand lower bound $Q_7\ge12$, not a substitute for an unproved asymptotic extrapolation.

7. Exact wall

(a). The cyclic construction gives

\pi(K_4^3)\ge\frac59.

Monotonicity of finite densities and the exact $n=9$ value give only

\pi(K_4^3)\le\frac{54}{84}=\frac9{14}.

This finite upper bound is much too weak to meet $5/9$. The precise missing lemma for this route is a uniform inequality

\operatorname{ex}_3(n,K_4^3) \le\left(\frac59+o(1)\right)\binom n3

for all large $n$; that is Turán's tetrahedron conjecture itself. No finite table, however far extended, supplies the required uniformity without an additional stability/finite-forcing theorem.

(d). As an exploratory boundary check only, an 8-worker CP-SAT feasibility run for a 44-block $\operatorname{Cov}(10,7,6)$ cover returned UNKNOWN after 30 seconds, about 3.9 million branches and 0.55 million conflicts. It is not part of any claimed certificate.

(c, cost estimate). A symmetry-aware exact certificate for the next finite case could reasonably consume core-hours rather than seconds; a first bounded budget would be roughly 1–10 core-hours. Even a successful finite computation would not resolve the density. Closing #712 for one pair instead requires a matching asymptotic construction and uniform upper-bound proof (or a certified flag-algebra/stability argument with the required exact limiting step).

PARTIAL: Proved the exact covering-design reduction, closed three near-diagonal finite regimes (including all ex_3(n,K_{n-2}^3)), and independently certified ex_3(n,K_4^3)=3,7,14,23,36,54 for n=4,...,9; no complete-hypergraph Turán density is determined.

This is the AI working report, labelled by outcome — not an independently verified claim unless marked PROVED. ← ledger