THE FOLD / CO-OP / THE PULL REQUEST / THE HALL
THE HALL
everyone can be matched iff no k suitors share only k-1 options
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Hall’s marriage theorem answers: when can everyone be paired up? Picture people, each with a list of acceptable partners from another group. A perfect matching — everyone gets an acceptable partner, no partner shared — exists if and only if Hall’s condition holds: every group of k people together must have at least k acceptable partners between them.
The reason one direction is obvious — if some k people collectively know only k−1 options, they cannot all be matched, by pigeonhole. The deep half is that this single condition is also enough: if it never fails, a full matching always exists. It is equivalently the theorem of systems of distinct representatives (pick one distinct element from each of several sets iff every k sets have ≥ k elements in their union), and it sits under scheduling, assignment, and network flow.
LIT verified live: a maximum matching computed by augmenting paths reaches everyone exactly when Hall’s condition (checked over every subset) holds — a perfect case matches all, a deficient case fails both, in agreement (window.__hall). FIG no framing; the matching, the subset condition, and their equivalence are exact.
The reason one direction is obvious — if some k people collectively know only k−1 options, they cannot all be matched, by pigeonhole. The deep half is that this single condition is also enough: if it never fails, a full matching always exists. It is equivalently the theorem of systems of distinct representatives (pick one distinct element from each of several sets iff every k sets have ≥ k elements in their union), and it sits under scheduling, assignment, and network flow.
LIT verified live: a maximum matching computed by augmenting paths reaches everyone exactly when Hall’s condition (checked over every subset) holds — a perfect case matches all, a deficient case fails both, in agreement (window.__hall). FIG no framing; the matching, the subset condition, and their equivalence are exact.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this in THE PULL REQUEST — the co-op domain of matching work to a willing reviewer. Hall’s theorem is the pull-request question exactly: can every change be assigned an acceptable reviewer at once, or does some cluster overload too few? AVAN (AI) built the instrument: the augmenting-path matcher, the subset checker, the obstruction-certificate inverse.
The weave: David names the seat (match all requests or find the jam); I make the matching succeed precisely when Hall holds and expose the blocking set when it doesn’t — the count in 1D, the bipartite matcher in 2D, the certificate inverse in 3D. The sphere is the seam. Credit: Philip Hall (1935); König’s theorem and Berge’s augmenting paths.
The weave: David names the seat (match all requests or find the jam); I make the matching succeed precisely when Hall holds and expose the blocking set when it doesn’t — the count in 1D, the bipartite matcher in 2D, the certificate inverse in 3D. The sphere is the seam. Credit: Philip Hall (1935); König’s theorem and Berge’s augmenting paths.
3 ONE DIMENSION
Take any group of k people and pool their acceptable partners. Hall’s test on a line: the pooled options must number at least k. The moment a group of k pools only k−1, the matching is doomed — drawn as a bar that falls short.
4 TWO DIMENSIONS · INTERACTIVE
A bipartite graph — people on the left, partners on the right, edges for “acceptable.” The instrument finds the maximum matching and checks Hall’s condition. When it holds, a full matching lights up green; when it fails, the blocking subset (k people, < k options) glows red.
5 THREE DIMENSIONS + AVAN’S INVERSE
The bipartite graph turning, the green forward result: a perfect matching — a certificate that everyone can be paired.
AVAN’s addition (the inverse-companion): when no matching exists, the magenta is the proof of impossibility — a specific set of k people whose combined options number only k−1. Hall’s theorem is a certificate duality: either there is a full matching, or there is a deficient set that proves there cannot be — exactly one, never both, never neither. Finding a matching is the forward search; its inverse is finding the bottleneck that blocks it, and the theorem guarantees the inverse witness always exists when the forward fails. This is a min-max law (König, and LP duality underneath): the largest matching equals the smallest cover, so a shortfall of exactly one somewhere is the whole obstruction. Green is the pairing that works; magenta is the overloaded cluster that makes pairing impossible; and one of the two is always the honest answer. To fail to match is not vague bad luck — it is a nameable, exhibitable jam.
LIT Genuine Hall's marriage theorem (Philip Hall 1935; related to Konig's theorem and Berge's augmenting paths). Verified live: a maximum matching computed by augmenting paths reaches all left vertices exactly when Hall's condition (checked over every subset of the left) holds — a perfect case matches all 3 and Hall holds, a deficient case matches only 2 and Hall fails, in agreement across cases (window.__hall.theoremHolds true). The matching, the subset condition, and their equivalence are exact.
FIG No framing: the augmenting-path matching, the exhaustive Hall-condition check, and their exact equivalence (perfect matching <=> condition holds) are real and verified in-browser. The AVAN inverse is the genuine min-max duality (Konig / LP): either a matching exists or a deficient set proves it cannot — exactly one, an exhibitable certificate either way, not asserted.
FIG No framing: the augmenting-path matching, the exhaustive Hall-condition check, and their exact equivalence (perfect matching <=> condition holds) are real and verified in-browser. The AVAN inverse is the genuine min-max duality (Konig / LP): either a matching exists or a deficient set proves it cannot — exactly one, an exhibitable certificate either way, not asserted.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE PULL REQUEST · David Lee Wise (ROOT0), with AVAN