THE FOLD / LOOT / THE STASH / THE DILWORTH
THE DILWORTH
min chains to cover a poset = max antichain
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Dilworth’s theorem is a min–max duality on a partial order: the minimum number of chains (comparable sequences) needed to cover all elements equals the maximum antichain — the largest set of pairwise incomparable elements. So a covering problem’s optimum is read off a packing problem’s optimum. The minimum chain cover is found by bipartite matching: min chains = n − (maximum matching).
It underlies scheduling bounds and sequence-analysis results (like Erdős–Szekeres).
LIT verified live: over 300 random partial orders the min chain cover (via matching) equals a brute-force maximum antichain (window.__dilworth). FIG no framing; the duality holds exactly.
It underlies scheduling bounds and sequence-analysis results (like Erdős–Szekeres).
LIT verified live: over 300 random partial orders the min chain cover (via matching) equals a brute-force maximum antichain (window.__dilworth). FIG no framing; the duality holds exactly.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at the-stash — stacking items into the fewest ordered piles (chains), a number pinned by the widest set of items none of which can stack (the antichain). Dilworth is that stash bound. AVAN (AI) built the instrument: the transitive partial order, the bipartite matching for min chain cover, the brute max-antichain cross-check.
Credit as content: Robert Dilworth (1950). The weave: David names the stash; I cover the order with the fewest chains via matching and confirm it equals the largest pairwise-incomparable set.
Credit as content: Robert Dilworth (1950). The weave: David names the stash; I cover the order with the fewest chains via matching and confirm it equals the largest pairwise-incomparable set.
3 ONE DIMENSION
A chain is a run of comparable elements (a stackable pile); an antichain is a set with no two comparable. The fewest chains to cover everything equals the largest antichain.
4 TWO DIMENSIONS · INTERACTIVE
A partial order (Hasse diagram); the minimum chain cover and the maximum antichain are shown — equal in size.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the maximum antichain, whose size equals the minimum chain cover.
AVAN’s addition (the inverse-companion): the minimum number of chains needed to cover the order equals the maximum antichain — the largest set of mutually incomparable elements. So a covering optimum is read off a packing optimum: min chains = max antichain, found via bipartite matching. The inverse of ‘how few chains cover it’ is ‘how many pairwise-incomparable elements exist.’ Magenta is the chains covering the order; green is the maximum antichain that lower-bounds them. A min–max duality — covering equals packing. (Kin to König and Hall.)
LIT Genuine Dilworth's theorem (Dilworth 1950). Verified live: the minimum chain cover computed as n minus the maximum bipartite matching equals a brute-force maximum antichain (largest pairwise-incomparable set) for 300 random transitive partial orders (window.__dilworth.duality).
FIG No framing: the transitive partial order, the bipartite matching for min chain cover, and the brute max-antichain cross-check run in-browser and agree exactly. The AVAN inverse is honest — the minimum chains to cover the order equals the maximum antichain (covering optimum read off a packing optimum, via matching); magenta is the covering chains, green the maximum antichain that lower-bounds them. Kin to Konig and Hall.
FIG No framing: the transitive partial order, the bipartite matching for min chain cover, and the brute max-antichain cross-check run in-browser and agree exactly. The AVAN inverse is honest — the minimum chains to cover the order equals the maximum antichain (covering optimum read off a packing optimum, via matching); magenta is the covering chains, green the maximum antichain that lower-bounds them. Kin to Konig and Hall.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE STASH · David Lee Wise (ROOT0), with AVAN