Research · Papers · Exact answers in open problems · MF-194
Vertex-deletion averaging ladder for the Turán (3,4)-problem
ex(n) ≤ ⌊n·ex(n-1)/(n-3)⌋ for ex(n, K_4^(3)); given ex(13) = 174, ex(14) ≤ 221 leaving a gap of at most one triple
Published 2026-09-06
For everyone
Plain summary
The Turán (3,4)-problem asks for the maximum number of 3-element subsets (triples) chosen from n items without containing all 4 triples on any 4-item subset. Deleting one item at a time from an optimal configuration shows that the total number of triples on n items cannot exceed floor(n * ex(n-1) / (n-3)), where ex(k) is the maximum triple count on k items.
Propagating this recurrence across small parameters shows that several conjectured bounds follow automatically from earlier values. In particular, if ex(13) = 174 triples, then ex(14) can be at most 221 triples. Because a known construction achieves 220 triples on 14 items, the remaining open gap is exactly one triple.
Caveat: this recurrence is the standard Katona-Nemetz-Simonovits monotonicity argument; the underlying mechanism is likely folklore.
Result
Let ex(n) = ex(n, K_4^(3)) be the maximum number of edges in a 3-uniform hypergraph on n vertices containing no complete subhypergraph on 4 vertices. For every vertex v in an extremal configuration with t = ex(n) triples, vertex deletion gives:
deg(v) >= t - ex(n-1)
Summing over all n vertices yields the recursive upper bound:
ex(n) <= floor(n * ex(n-1) / (n-3))
Under Turán's conjectured values, this recurrence gives:
- ex(8) <= 36
- ex(9) <= 54 (from ex(8) = 36)
- ex(12) <= 136
- ex(15) <= 275 (from ex(14) = 220)
The only parameters in this range requiring independent upper-bound proofs are n = 10, 11, 13, 14. Given ex(13) = 174, the ladder gives ex(14) <= floor(14 * 174 / 11) = 221. Against Turán's lower bound of 220, the open window at n = 14 is at most one triple. A proof that ex(14) = 220 implies ex(15) = 275 without additional search.
Strengthened lemma clauses L2 (codegree deletion) and L3 (triple deletion) follow from the same averaging scheme.
Setting and definitions
Let H = (V, E) be a 3-uniform hypergraph on n vertices. The Turán number ex(n, K_4^(3)) is the maximum cardinality |E| such that no 4-element subset of V induces all 4 possible triples. Write ex(n) = ex(n, K_4^(3)).
For v in V, the degree deg(v) is the number of triples in E incident to v. The subhypergraph H - v is obtained by deleting v and all triples containing v.
Method
Let H be an extremal K_4^(3)-free 3-graph on n vertices with t = ex(n) edges. For any v in V(H), the subhypergraph H - v has n - 1 vertices and t - deg(v) edges. Because H - v is K_4^(3)-free, its edge count satisfies:
t - deg(v) <= ex(n-1) ==> deg(v) >= t - ex(n-1)
Summing over all n vertices gives:
3t = sum_{v in V} deg(v) >= n * (t - ex(n-1))
Rearranging terms:
(n - 3) * t <= n * ex(n-1)
Dividing by n - 3 and taking the integer floor yields ex(n) <= floor(n * ex(n-1) / (n-3)).
Analogous double-counting over vertex pairs and triples produces the strengthened clauses L2 (codegree constraints) and L3 (triple deletion constraints). L2 and L3 were unit-tested for consistency at n in {6, 7, 8, 9}.
Receipt artifacts: lanes/turan-14/BANK-CANDIDATES.md (TUR-01), REPORT.md.
Discussion
This entry carries a CAVEAT verdict because its novelty is unverified; the bound is the Katona-Nemetz-Simonovits monotonicity argument evaluated at exact small orders.
The arithmetic consequence ex(14) <= 221 (one triple above the lower bound 220) directly follows from ex(13) = 174. The ladder isolates where non-trivial structure remains: resolving n = 14 at 220 immediately closes n = 15 at 275, whereas the ladder cannot independently close n = 10, 11, 13, or 14.
For everyone — the takeaway
What this means
Exact hypergraph Turán numbers are hard to compute because the search space explodes with vertex count. The vertex-deletion ladder removes the need to search certain orders independently: proving n = 14 has at most 220 triples immediately settles n = 15 at 275 triples. For 14 vertices, the bound limits the unresolved question to whether a single extra triple can fit into the configuration.
Attribution and prior art
Prior art: This result applies the standard Katona-Nemetz-Simonovits monotonicity argument to exact values. While the one-triple-wide observation at n = 14 was not found in prior literature, its novelty remains unverified, and this entry is recorded for completeness rather than as a novel claim. Sources: Katona, Nemetz, Simonovits 1964 · Turan 1941
Register references
- Register entry: MF-194
- Receipt:
lanes/turan-14/BANK-CANDIDATES.md(TUR-01) - Receipt:
REPORT.md - Prior art: Katona-Nemetz-Simonovits monotonicity argument
Every artifact named above is bundled in, or hashed by, this paper's evidence pack below.
Evidence pack
Everything needed to check this entry against its receipts: the register text, a manifest with a SHA-256 hash for every named receipt, and 2 of 2 receipt files bundled (20 KB). Anything not bundled is still hashed in the manifest and lives in the compute-box working trees.
Changelog
Last reviewed 2026-09-06
- 2026-09-06Published on this site.