THE FOLD / GRIND / THE GRINDSTONE / THE ERDOS-SZEKERES
THE ERDOS-SZEKERES
order you cannot escape
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
The Erdős–Szekeres theorem is order you cannot escape. In any sequence of (r−1)(s−1)+1 distinct numbers, there must be an increasing subsequence of length r or a decreasing one of length s — no matter how you scramble it. Ten numbers (3·3+1) always hide a monotone run of four. The proof is pure pigeonhole: label each term by the longest increasing run ending there and the longest decreasing run ending there; if both stayed small there would be too few labels for the terms. And the bound is tight — a sequence of exactly (r−1)(s−1) can dodge both.
LIT verified live: 4,000 random sequences of length (r−1)(s−1)+1 always contain an increasing run of r or a decreasing run of s, and a block construction of length (r−1)(s−1) achieves exactly r−1 and s−1 (window.__erdos_szekeres). FIG no framing; longest runs are computed by dynamic programming in-browser.
LIT verified live: 4,000 random sequences of length (r−1)(s−1)+1 always contain an increasing run of r or a decreasing run of s, and a block construction of length (r−1)(s−1) achieves exactly r−1 and s−1 (window.__erdos_szekeres). FIG no framing; longest runs are computed by dynamic programming in-browser.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at the-grindstone — grind through any long enough list and order is forced to surface; you cannot file it away. AVAN (AI) built the instrument: compute the longest increasing and decreasing subsequences by DP, confirm the guarantee over random inputs, and build the tight block sequence that just barely escapes it.
Credit as content: Paul Erdős & George Szekeres (1935), a founding result of Ramsey theory. The weave: David names the grindstone; I show the monotone run is unavoidable above the threshold and that one below it can still slip through.
Credit as content: Paul Erdős & George Szekeres (1935), a founding result of Ramsey theory. The weave: David names the grindstone; I show the monotone run is unavoidable above the threshold and that one below it can still slip through.
3 ONE DIMENSION
A sequence as bars; the longest increasing run (green) and longest decreasing run (magenta) are traced — one of them always reaches the guaranteed length.
4 TWO DIMENSIONS · INTERACTIVE
Draw a fresh sequence of (r−1)(s−1)+1 terms; the guarantee holds every time. Or show the tight block sequence that dodges both by one.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the monotone run the sequence is forced to contain.
AVAN’s addition (the inverse-companion): don’t hunt for the run — label and count. The inverse of ‘search for a long increasing or decreasing streak’ is ‘give each term its (up,down) label; with too few labels two terms must collide, and that forces the run.’ Magenta is the label grid; green is the forced streak. Pigeonhole leaves no exit.
LIT Genuine Erdős–Szekeres theorem (Paul Erdős & George Szekeres, 1935), a founding Ramsey-theory result: any sequence of (r−1)(s−1)+1 distinct reals has an increasing subsequence of length r or a decreasing one of length s, and the bound is tight. Verified live: 4000 random sequences all satisfy it (window.__erdos_szekeres.alwaysFound) and the block construction of length (r−1)(s−1) has LIS=r−1, LDS=s−1 (.tightConstruction).
FIG No framing: longest increasing/decreasing subsequences are computed by DP in-browser, over random inputs and the tight construction. The AVAN inverse is honest — labelling each term by its (up,down) run-lengths and invoking pigeonhole (too few distinct labels) is the actual proof that the run is forced, not a search; magenta is the label grid, green the forced streak. Pigeonhole leaves no exit.
FIG No framing: longest increasing/decreasing subsequences are computed by DP in-browser, over random inputs and the tight construction. The AVAN inverse is honest — labelling each term by its (up,down) run-lengths and invoking pigeonhole (too few distinct labels) is the actual proof that the run is forced, not a search; magenta is the label grid, green the forced streak. Pigeonhole leaves no exit.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE GRINDSTONE · David Lee Wise (ROOT0), with AVAN