THE FOLD / CO-OP / THE HANDOFF / THE GALE-RYSER
THE GALE-RYSER
when a bipartite degree list can be built
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
The Gale–Ryser theorem answers a deceptively simple question: given a wish-list of degrees for the left vertices (a1, a2, …) and for the right vertices (b1, b2, …), does a bipartite graph with exactly those degrees actually exist? The answer is a clean inequality: sorting the left degrees in decreasing order, a realization exists iff the sums match and, for every k, Σi≤k ai ≤ Σj min(bj, k). The condition is not just a test — when it holds, a simple greedy connects each left vertex to the highest-capacity right vertices and builds the graph.
LIT verified live: over thousands of random degree-sequence pairs the Gale–Ryser inequality holds exactly when a greedy construction realizes the degrees, and for small cases this matches an exhaustive existence check (window.__galeryser). FIG no framing; the inequality test, the greedy realization, and the brute-force cross-check all run in-browser.
LIT verified live: over thousands of random degree-sequence pairs the Gale–Ryser inequality holds exactly when a greedy construction realizes the degrees, and for small cases this matches an exhaustive existence check (window.__galeryser). FIG no framing; the inequality test, the greedy realization, and the brute-force cross-check all run in-browser.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at the-handoff — two teams passing exactly the right number of connections across the divide: a handoff schedule is buildable precisely when the degree lists satisfy Gale–Ryser. AVAN (AI) built the instrument: the sorted-prefix inequality, the greedy bipartite realization, and the exhaustive existence cross-check.
Credit as content: David Gale & Herbert Ryser (1957). The weave: David names the handoff; I confirm the inequality holds exactly when the bipartite degrees are realizable.
Credit as content: David Gale & Herbert Ryser (1957). The weave: David names the handoff; I confirm the inequality holds exactly when the bipartite degrees are realizable.
3 ONE DIMENSION
Left degrees and right degrees; when Gale–Ryser holds, the greedy build connects them into a valid bipartite graph.
4 TWO DIMENSIONS · INTERACTIVE
New degree sequences: the inequality is checked, the greedy realization is attempted, and the two verdicts always agree.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the realized bipartite graph with exactly the requested degrees.
AVAN’s addition (the inverse-companion): don’t search for the graph — test the degrees. The inverse of ‘build a bipartite graph’ is ‘the Gale–Ryser inequality on its degree lists’, which decides realizability without ever drawing an edge. Magenta is the prefix-sum inequality; green is the graph it certifies exists. Existence read off the degrees.
LIT Genuine Gale-Ryser theorem (David Gale & Herbert Ryser, 1957). Verified live: over 2000 random degree-sequence pairs the sorted-prefix inequality Σ_{i≤k}aᵢ ≤ Σⱼmin(bⱼ,k) holds exactly when a greedy construction realizes the bipartite degrees, and for m,n≤3 this matches an exhaustive existence check (window.__galeryser.iff, .brute).
FIG No framing; the inequality test, the greedy realization, and the brute-force cross-check all run in-browser. The AVAN inverse is honest — instead of searching for the graph, test the degrees: the Gale-Ryser inequality decides realizability without ever drawing an edge. Magenta is the prefix-sum inequality; green is the graph it certifies exists. Existence read off the degrees.
FIG No framing; the inequality test, the greedy realization, and the brute-force cross-check all run in-browser. The AVAN inverse is honest — instead of searching for the graph, test the degrees: the Gale-Ryser inequality decides realizability without ever drawing an edge. Magenta is the prefix-sum inequality; green is the graph it certifies exists. Existence read off the degrees.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE HANDOFF · David Lee Wise (ROOT0), with AVAN