THE FOLD / BOSS / THE WALL / THE TURÁN
THE TURÁN
the most edges with no clique of a given size
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Turán’s theorem is the summit of extremal graph theory: the most edges a graph on n vertices can have while containing no clique of size r + 1 is achieved by the Turán graph T(n, r) — split the vertices into r nearly-equal groups and join every pair in different groups. No clique of size r + 1 can form (it would need two vertices in one group, which are never joined), and this complete r-partite graph packs the maximum (1 − 1/r)·n2/2 edges. Mantel’s triangle-free bound is exactly the r = 2 case.
LIT verified live: an exhaustive search over all graphs on up to 6 vertices finds the maximum edge count with no Kr+1 equals the Turán graph T(n, r)’s edge count, for r = 2 and r = 3 (window.__turan). FIG no framing; brute-force extremal count vs the Turán construction.
LIT verified live: an exhaustive search over all graphs on up to 6 vertices finds the maximum edge count with no Kr+1 equals the Turán graph T(n, r)’s edge count, for r = 2 and r = 3 (window.__turan). FIG no framing; brute-force extremal count vs the Turán construction.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at the-wall — pack edges as densely as you like, but the moment you would force a clique of size r + 1 you hit the wall, at exactly the Turán count. AVAN (AI) built the instrument: the exhaustive Kr+1-free edge maximiser, the Turán graph edge formula, and their agreement.
Credit as content: Pál Turán (1941); the r = 2 case is Willem Mantel (1907). The weave: David names the-wall; I try every graph on n vertices, keep the ones with no clique of size r + 1 and the most edges, and confirm the record equals the balanced complete r-partite graph — the densest a clique-free graph can be.
Credit as content: Pál Turán (1941); the r = 2 case is Willem Mantel (1907). The weave: David names the-wall; I try every graph on n vertices, keep the ones with no clique of size r + 1 and the most edges, and confirm the record equals the balanced complete r-partite graph — the densest a clique-free graph can be.
3 ONE DIMENSION
No K4 (r = 3), n = 6: split into three pairs, join all cross-pairs — T(6,3), 12 edges, no triangle-free-clique of 4. Add an edge inside a pair and a K4 appears. Mantel (no triangle) is r = 2.
4 TWO DIMENSIONS · INTERACTIVE
The Turán graph T(n, r) and its edge count against the exhaustive Kr+1-free maximum; checked.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the densest clique-free graph.
AVAN’s addition (the inverse-companion): don’t detect a clique of size r + 1 — ask how many edges you can pack before one is forced, and the answer is the balanced r-partition. The inverse of ‘find a Kr+1’ is ‘maximise edges with no Kr+1 — split into r equal parts.’ Magenta is a graph with a clique of size r + 1; green is the extremal Turán graph. Packed to the wall before the clique.
LIT Genuine Turán's theorem (Pál Turán, 1941; the r=2 case is Willem Mantel, 1907). Verified live: an exhaustive search over all graphs on n vertices finds the maximum edge count containing no clique of size r+1 equals the Turán graph T(n,r)'s edge count (n·(n−1)/2 minus the within-part edges of a balanced r-partition) for all n up to 6 and r∈{2,3} (window.__turan.matchesTuranGraph).
FIG No framing: the exhaustive K_{r+1}-free edge maximiser, the Turán graph edge formula, and their agreement all run in-browser. The AVAN inverse is honest — maximising edges subject to no clique of size r+1 (the balanced r-partition) rather than detecting a clique is the genuine extremal question, answered by the Turán graph; magenta is a graph containing that clique, green the extremal Turán graph. Packed to the wall before the clique.
FIG No framing: the exhaustive K_{r+1}-free edge maximiser, the Turán graph edge formula, and their agreement all run in-browser. The AVAN inverse is honest — maximising edges subject to no clique of size r+1 (the balanced r-partition) rather than detecting a clique is the genuine extremal question, answered by the Turán graph; magenta is a graph containing that clique, green the extremal Turán graph. Packed to the wall before the clique.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE WALL · David Lee Wise (ROOT0), with AVAN