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

Erdős problem #500 — wave 9n

Access/research date: 2026-07-28 UTC.

Claim labels used below:

(a) elementary-rigorous: proved here from elementary facts.
(b) rigorous modulo named theorem/source certificate: the dependency is

named explicitly.

(c) plausible/structural-unverified: a heuristic or missing reduction,

not a theorem.

(d) computational-only: established only by the stated finite

computation or source inspection.

0. Mandatory live-page gate

(d, live-page inspection) I fetched the live problem page, its LaTeX view, and its revision history through the Bright Data browser path. Direct datacenter curl was not used for this gate.

The verbatim current statement is:

What is $\mathrm{ex}_3(n,K_4^3)$? That is, the largest number of $3$-edges which can placed on $n$ vertices so that there exists no $K_4^3$, a set of 4 vertices which is covered by all 4 possible $3$-edges.

The page's mathematical context, verbatim from its LaTeX view, is:

A problem of Tur\'{a}n. Tur\'{a}n observed that dividing the vertices into three equal parts $X_1,X_2,X_3$, and taking the edges to be those triples that either have exactly one vertex in each part or two vertices in $X_i$ and one vertex in $X_{i+1}$ (where $X_4=X_1$) shows that \[ > \mathrm{ex}_3(n,K_4^3)\geq > \left(\frac{5}{9}+o(1)\right)\binom{n}{3}. > \] This is probably the truth. The current best upper bound is \[ > \mathrm{ex}_3(n,K_4^3)\leq0.5611666\binom{n}{3}, > \] due to Razborov $\cite{Ra10}$.
See also [712] for the general case.

The live status is OPEN — $500. The page says it was last edited 05 October 2025 and displays:

comments: 0;
claimed proofs: 0;
Likes this problem: None;
Interested in collaborating: None;
Currently working on this problem: None;
This problem looks difficult: None;
This problem looks tractable: None;
The results could be formalisable: None;
I am working on formalising the results: None;
formalised statement: No;
related sequence: A140462.

It attaches the source markers [Er61] [Er71, p. 104] [Er74c, p. 81] [Er81], cites [Ra10] for the upper bound, and uses the tags graph theory, hypergraphs, and turan number. These are metadata/context, not additions to the statement.

The stop condition therefore did not trigger.

1. Primary-source and certificate audit

1.1 The status is genuinely open

(d, source inspection) Alexander Razborov's paper On 3-Hypergraphs with Forbidden 4-Vertex Configurations, SIAM J. Discrete Math. 24 (2010), 946–963, exists with exactly the bibliographic data given on the tracker. Its introduction calls the tetrahedron case unresolved, and its conclusion says that proving or disproving the $4/9$ lower-density conjecture in the complementary formulation remains a major challenge.

(b, Razborov's Theorem 1) The rigorous main theorem in that paper solves a restricted induced problem: in the usual maximum-edge formulation it additionally forbids a four-vertex set spanning exactly one edge. It does not solve the unrestricted $K_4^3$-free problem.

(b, Balogh–Clemen–Lidický) Balogh, Clemen and Lidický, Solving Turán's tetrahedron problem for the $\ell_2$-norm, arXiv:2108.10408, later J. London Math. Soc. 106 (2022), 60–84, solve a different objective: the sum of squared pair-codegrees. Their abstract explicitly contrasts this with the original $\ell_1$ edge-count problem. This related advance does not close problem #500.

(d, prior finite computation) Jing Zou's 1992 thesis Computational techniques in Turan problems states in its abstract that it determines $T(13,4,3)$, confirms the previously unpublished values $T(n,4,3)$ for $n=10,11,12$, and obtains all minimum systems for $n<12$. Thus the small values independently reproved below are not claimed as new literature.

1.2 The live upper-bound decimal is not supported by its citation

This audit found a material metadata problem.

(d, primary-source inspection) On printed p. 947, Razborov reports the complementary numerical computation

\pi_{\min}(I_4^3)\geq0.438334,

which corresponds to

\pi(K_4^3)\lesssim 1-0.438334=0.561666.

The next paragraph explicitly says that this floating-point calculation was not converted into a rigorous proof in that paper. It does not state $0.5611666$.

(b, exact Flagmatic certificate computation) Emil Vaughan's Flagmatic User's Guide, version 1.5, gives the exact rationalized level-6 computation

\pi(K_4^3)\leq \frac{2246662543771}{4000000000000} =0.56166563594275. \tag{1.1}

The accompanying Flagmatic page describes its listed non-tight bounds as exact rational computations and originally supplied a JSON certificate. Its reproduction transcript uses 964 admissible six-vertex 3-graphs, rationalizes the SDP matrices with denominator $10^7$, and runs verify_bound.py.

(a, arithmetic; d, source search) The number in (1.1) exceeds the live page's decimal $0.5611666$ by exactly

\frac{1996143771}{4000000000000} =0.00049903594275.

Exact-phrase searches for 0.5611666, inspection of Ra10, and inspection of the Flagmatic documentation found no primary source for the tracker's smaller number. The likely explanation is a transposed/inserted decimal digit, but that explanation is an inference, not a fact.

There is a second precision issue: the tracker writes its upper bound as a literal finite-$n$ inequality. That cannot be right, since $\mathrm{ex}_3(4,K_4^3)=3$, and $3/\binom43=3/4$. The sourced result is a Turán-density bound, equivalently

\mathrm{ex}_3(n,K_4^3) \leq\left(0.56166563594275+o(1)\right)\binom n3.

Accordingly, this report records the live page exactly as required but uses (1.1), not $0.5611666$, in the mathematical gap calculation. The primary and certificate searches did not uncover a claimed proof, a falsification, or a later solution.

2. Exact complement reduction

Let $C(v,k,t)$ denote the least number of $k$-subsets of a $v$-set whose union-by-inclusion covers every $t$-subset.

Proposition 2.1

(a) For every $n\geq4$,

\boxed{\quad \mathrm{ex}_3(n,K_4^3) =\binom n3-C(n,n-3,n-4). \quad} \tag{2.1}

Proof. Let $H\subseteq\binom V3$ be $K_4^3$-free and put $F=\binom V3\setminus H$. The condition is exactly that every four-set $Q$ contains some $E\in F$. Complement every $E\in F$ inside $V$, obtaining the $(n-3)$-block $V\setminus E$. If $S=V\setminus Q$, then $|S|=n-4$, and

E\subseteq Q\quad\Longleftrightarrow\quad S\subseteq V\setminus E.

Thus the complements of $F$ form a $C(n,n-3,n-4)$-cover. The operation is reversible, so minimizing $|F|$ gives (2.1). $\square$

This reduction is useful because covering numbers have a simple deletion recurrence.

Lemma 2.2 (Schönheim deletion bound)

(a) For $1\leq t\leq k\leq v$,

C(v,k,t)\geq \left\lceil\frac{v}{k}C(v-1,k-1,t-1)\right\rceil. \tag{2.2}

Proof. Fix a point $x$. The blocks containing $x$, after deleting $x$, cover all $(t-1)$-sets on the other $v-1$ points. Hence the block-degree of every point is at least $C(v-1,k-1,t-1)$. Sum the degrees over all $v$ points; every block is counted $k$ times. $\square$

3. A short exact base case

Lemma 3.1

(a) $C(7,4,3)=12$.

Proof. A 12-block cover is supplied by complementing the 12 nonedges in Turán's seven-vertex construction; the standalone checker lists and checks it.

For the lower bound, suppose that eleven 4-blocks cover all triples of a seven-set. Write $d_{xy}$ for the number of blocks through a pair $\{x,y\}$. There are five triples through that pair, while each block through it covers exactly two of them. Therefore $d_{xy}\geq3$. Since each 4-block contains six pairs,

\sum_{\{x,y\}}d_{xy}=6\cdot11=66.

Put $\delta_{xy}=d_{xy}-3$. Then

\delta_{xy}\geq0,\qquad \sum_{\{x,y\}}\delta_{xy}=3. \tag{3.1}

Let $d_x$ be the number of blocks through $x$, and set $q_x=\sum_{y\ne x}\delta_{xy}$. Every block through $x$ contains three pairs through $x$, so

3d_x=\sum_{y\ne x}d_{xy}=18+q_x. \tag{3.2}

Thus every $q_x$ is a nonnegative multiple of three. Also $\sum_xq_x=2\sum_{xy}\delta_{xy}=6$. A single positive $q_x$ is impossible, because every positive $\delta_{xy}$ has two endpoints. Consequently exactly two vertices, say $a,b$, have $q=3$, all other vertices have $q=0$, and (3.1) forces

\delta_{ab}=3,\qquad d_{ab}=6,\qquad d_a=d_b=7. \tag{3.3}

Of the seven blocks through $a$, six contain $b$ and exactly one does not. Delete $a$ from those seven blocks. The resulting seven triples on the other six points must cover every pair there. Let $X=V\setminus\{a,b\}$, so $|X|=5$. Each of the six residual triples containing $b$ covers only one pair internal to $X$. The unique residual triple avoiding $b$ covers three pairs internal to $X$. They can therefore cover at most $6+3=9$ of the $\binom52=10$ pairs of $X$, a contradiction. Hence eleven blocks do not suffice. $\square$

The pair-excess argument is the nontrivial finite ingredient. Plain application of (2.2) would give only $C(7,4,3)\geq11$.

4. Exact independently checked table through $n=9$

Start with $C(4,1,0)=1$. Lemma 2.2, Lemma 3.1, and then Lemma 2.2 again give

\begin{aligned} C(5,2,1)&\geq\left\lceil\frac52\right\rceil=3,\\ C(6,3,2)&\geq\left\lceil\frac63\cdot3\right\rceil=6,\\ C(7,4,3)&=12,\\ C(8,5,4)&\geq\left\lceil\frac85\cdot12\right\rceil=20,\\ C(9,6,5)&\geq\left\lceil\frac96\cdot20\right\rceil=30. \end{aligned} \tag{4.1}

Turán's balanced cyclic construction attains every one of these bounds. For consecutive cyclic part sizes $a,b,c$, its edge count is

abc+\binom a2b+\binom b2c+\binom c2a. \tag{4.2}

Together with the trivial cases $n\leq3$, Proposition 2.1 gives:

| $n$ | complement cover size | $\mathrm{ex}_3(n,K_4^3)$ | |---:|---:|---:| | 0 | — | 0 | | 1 | — | 0 | | 2 | — | 0 | | 3 | — | 1 | | 4 | 1 | 3 | | 5 | 3 | 7 | | 6 | 6 | 14 | | 7 | 12 | 23 | | 8 | 20 | 36 | | 9 | 30 | 54 |

(a) The table is a proof-level consequence of (2.1), (2.2), and Lemma 3.1.

(d, independent recomputation) The standalone verifier also proves the only exceptional base case by a complete set-cover search. By permutation symmetry it fixes one block to $0123$, branches on an uncovered triple, and tries every 4-block containing it. The only pruning uses

\left\lceil \frac{\#\text{ uncovered triples}} {\text{maximum new triples covered by one block}} \right\rceil.

It exhausts 11,170 memoized states and returns UNSAT for 11 blocks. It then constructs a 12-block witness, builds every cyclic hypergraph in the table, and checks all four-sets directly.

This table agrees with the old computational literature noted in §1.1; it is an independent compact certificate, not a new finite frontier.

5. A sharp three-colour-template regime

The next result is a genuine uniform restricted-regime theorem. It is not claimed to be new, but it cleanly identifies a large class in which no counterexample can occur.

Partition $V$ into three parts $V_0,V_1,V_2$. A colour-multiset template chooses some of the ten multisets of three colours and includes all triples whose colour multiset was chosen. For example, choosing

012,\quad 001,\quad112,\quad220

is Turán's cyclic template.

Theorem 5.1

(a) Let a three-colour-multiset template have $K_4^3$-free blow-ups whenever all three parts are sufficiently large. Every blow-up sequence from this template has asymptotic edge density at most $5/9$. If all three limiting part proportions are positive, equality holds only when the parts are balanced and the chosen types are the rainbow type together with a directed 3-cycle:

012,\quad iij,\quad jjk,\quad kki. \tag{5.1}

The reverse directed cycle is the second equality template.

Proof. Let the part proportions be $x,y,z$, with $x+y+z=1$. Represent the type $iij$ by an arc $i\to j$. Its normalized density contribution is $3x_i^2x_j$, while the rainbow type contributes $6xyz$.

Four vertices of one colour show that no pure type $iii$ is allowed. A $2+2$ colour pattern shows that $i\to j$ and $j\to i$ cannot both occur. If the rainbow type occurs, a $2+1+1$ pattern shows that no colour can have two outgoing arcs.

First suppose the rainbow type is absent. Sort $x\geq y\geq z$. Whatever the three pair orientations are, their unnormalized cubic is at most

\[ S=x^2y+x^2z+y^2z. \]

Put $z=t,\ y=t+a,\ x=t+a+b$, where $t,a,b\geq0$. Direct expansion gives

\begin{aligned} 5(x+y+z)^3-27S={}& 13a^3+6a^2b+45a^2t+3ab^2+18abt+81at^2+54t^3\\ &+b(5b^2-9bt+27t^2). \end{aligned} \tag{5.2}

The final quadratic is nonnegative because

\[ 20(5b^2-9bt+27t^2)=(10b-9t)^2+459t^2. \]

Thus $3S\leq5/9$.

Now include the rainbow type. The arc digraph has maximum outdegree one. With three arcs it must be a directed 3-cycle. Sort the three weights and call them $x\geq y\geq z$. The two possible cycle orientations have cubics $C$ and $C^{\mathrm{rev}}$, where

\[ C=x^2y+y^2z+z^2x. \]

Their difference is

C-C^{\mathrm{rev}}=(x-y)(x-z)(y-z)\geq0.

Thus the actual cycle cubic is at most $C$. With the same $t,a,b$ substitution,

\begin{aligned} 5(x+y+z)^3-27(C+2xyz)={}& 13a^3+6a^2b+18a^2t+3ab^2\\ &+18abt+5b^3+18b^2t\geq0. \end{aligned} \tag{5.3}

The normalized density is $3(C+2xyz)$, proving the $5/9$ bound. Equality in (5.3) forces $a=b=0$, hence $x=y=z=1/3$.

With two arcs and maximum outdegree one, the digraph is either an in-star or a directed path. For an in-star,

\frac{\text{density}}3 =z(x+y)^2\leq\frac4{27},

using

4(u+v)^3-27uv^2=(u+4v)(2u-v)^2\geq0.

Its density is at most $4/9$.

For a path $x\to y\to z$, put

g=\frac{\text{density}}3=x^2y+y^2z+2xyz.

For fixed $y$, substitute $z=1-y-x$:

\[ g=y[-x^2+(2-3y)x+y(1-y)]. \]

If $0\leq y\leq2/3$, this concave quadratic is at most

h(y)=\frac{y(5y^2-8y+4)}4\leq\frac4{25},

because

\frac4{25}-h(y)=\frac{(4-5y)(5y-2)^2}{100}\geq0.

If $y\geq2/3$, its vertex lies at $x\leq0$, so the maximum on the allowed interval is $y^2(1-y)\leq4/27<4/25$. Hence a path has density at most $12/25<5/9$. Zero or one arc is a subtemplate of one of these cases. Only the balanced full directed cycle can attain $5/9$. $\square$

(d, exhaustive structural check) The verifier independently enumerates all $2^{10}=1024$ templates and all 15 four-colour multisets. Exactly 45 templates are $K_4^3$-free, 11 are inclusion-maximal, and exactly two are the four-type equality templates in (5.1). It also expands (5.2), (5.3), the cyclic-difference identity, the in-star factorization, and the path factorization over exact rational arithmetic.

What Theorem 5.1 does and does not reduce

(a) Any construction beating $5/9$ cannot be a blow-up whose edge membership depends only on the multiset of three fixed colours.

(c) This does not reduce an arbitrary dense $K_4^3$-free hypergraph to three colours. Known density-$5/9$ constructions already exhibit much more fine-grained and iterated structure. A unique three-part stability statement at the conjectured threshold is therefore unavailable in this form.

6. Exact remaining wall

The certified asymptotic interval supported by the sources audited here is

\frac59 \leq\pi(K_4^3) \leq\frac{2246662543771}{4000000000000}. \tag{6.1}

Its exact width is

\frac{219962893939}{36000000000000} =0.006110080387194444\ldots. \tag{6.2}

The two concrete missing steps exposed by this run are:

Structural route. One would need a rigorous inequality reducing all

fine-grained/iterated local types of an arbitrary $K_4^3$-free 3-graph to an objective bounded by the template polynomial in §5, or an equally strong replacement. Theorem 5.1 only handles a single fixed three-colour quotient.

Flag-algebra route. The level-6 exact certificate stops at (1.1).

Closing the problem this way requires an exact rational/SOS certificate with objective $5/9$, not merely another floating-point improvement. The Flagmatic guide reports roughly 1.5–10 hours for typical level-7 3-graph computations, depending strongly on hardware and linear-algebra libraries. That is about 1.5–10 core-hours if CSDP is effectively single-core, or roughly $0.15–$3 at a realistic $0.10–$0.30 per high-memory core-hour, before rationalization and certificate checking. It exceeds this run's few-minute compute budget, and there is no evidence that level 7 would reach $5/9$.

The exact next finite case is not a useful novelty target: Zou's thesis already reports the values through $n=13$. A genuinely new finite result would have to start beyond that literature and would require an isomorph-free exhaustive certificate, not a solver incumbent.

7. Reproduction

The complete standalone verifier is runs/erdos500_wave9n_reverify.py. It uses only the Python standard library.

Run:

python runs/erdos500_wave9n_reverify.py

Observed output:

exact ex_3(n,K4^3), n=0..9: [0, 0, 0, 1, 3, 7, 14, 23, 36, 54]
C(7,4,3) <= 11 DFS states: 11170 (UNSAT)
K4-free three-colour templates: 45
equality templates (rainbow + directed 3-cycle): 2
all independent checks passed

Measured locally: 0.18 seconds elapsed, 14,856 KB maximum RSS. SHA-256:

76e8e5ae4223e0fc080c2c138c7bbfba4a78a3679cf7bce8d2a25ea0afefa291

PARTIAL: independently proved and checked the exact table through n=9 and the sharp 5/9 bound for every three-colour-multiset blow-up; the unrestricted density gap remains, and the live page's 0.5611666 decimal is unsupported by Ra10/Flagmatic.

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