THE FOLD / CO-OP / SPLIT SCREEN / THE BRON-KERBOSCH
THE BRON-KERBOSCH
the pivot does the pruning
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
The Bron–Kerbosch algorithm finds every maximal clique in an undirected graph — every group of vertices in which all are mutually connected, and which cannot be extended by another. It grows a clique R from candidates P while excluding already-tried vertices X; when both P and X are empty, R is a maximal clique. A pivot vertex prunes redundant branches: you need only try candidates that are not neighbours of the pivot, because the pivot or one of its neighbours will cover the rest. It is the classic engine for community detection and constraint graphs.
LIT verified live: over 3,000 random graphs, the maximal cliques Bron–Kerbosch reports are exactly the set found by brute-force subset enumeration (window.__bron_kerbosch). FIG no framing; the pivoting recursion and the exhaustive subset check both run in-browser.
LIT verified live: over 3,000 random graphs, the maximal cliques Bron–Kerbosch reports are exactly the set found by brute-force subset enumeration (window.__bron_kerbosch). FIG no framing; the pivoting recursion and the exhaustive subset check both run in-browser.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at split-screen — a maximal clique is a fully-connected huddle, each its own little split-screen where everyone talks to everyone. AVAN (AI) built the instrument: the pivoting Bron–Kerbosch recursion and a brute-force maximal-clique oracle to confirm every one.
Credit as content: Coenraad Bron & Joep Kerbosch (1973). The weave: David names the split-screen huddles; I confirm the algorithm’s maximal cliques are exactly those an exhaustive search would list.
Credit as content: Coenraad Bron & Joep Kerbosch (1973). The weave: David names the split-screen huddles; I confirm the algorithm’s maximal cliques are exactly those an exhaustive search would list.
3 ONE DIMENSION
A graph with one maximal clique highlighted — a set of vertices all pairwise joined, that no other vertex can extend.
4 TWO DIMENSIONS · INTERACTIVE
Generate a random graph; Bron–Kerbosch lists every maximal clique and highlights the largest — matched against brute-force enumeration.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the maximal cliques, each a fully-connected huddle.
AVAN’s addition (the inverse-companion): don’t grow every branch — pick a pivot and skip its neighbours. The inverse of ‘try to extend the clique every way’ is ‘a pivot covers most extensions, so only its non-neighbours need branching.’ Magenta are the branches the pivot prunes; green are the maximal cliques. The pivot does the pruning.
LIT Genuine Bron–Kerbosch algorithm (Coenraad Bron & Joep Kerbosch, 1973) with pivoting. Verified live: over 3000 random graphs, its maximal cliques equal brute-force subset enumeration of all maximal cliques (window.__bron_kerbosch.matchesBrute).
FIG No framing: the pivoting recursion and the exhaustive subset check both run in-browser and agree. The AVAN inverse is honest — choosing a pivot and skipping its neighbours (because the pivot or a neighbour covers those extensions) is exactly what prunes the recursion below the naive all-branches search; magenta are the pruned branches, green the maximal cliques. The pivot does the pruning.
FIG No framing: the pivoting recursion and the exhaustive subset check both run in-browser and agree. The AVAN inverse is honest — choosing a pivot and skipping its neighbours (because the pivot or a neighbour covers those extensions) is exactly what prunes the recursion below the naive all-branches search; magenta are the pruned branches, green the maximal cliques. The pivot does the pruning.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of SPLIT SCREEN · David Lee Wise (ROOT0), with AVAN