Does the K3 partition-ordinal property imply the Kn property? (Erdős–Hajnal, disproved by Darby/Schipperus/Larson)

Statement

For a countable ordinal $\alpha$, say $\alpha$ has property $P_m$ if $\alpha\to(\alpha,m)^2$: every red/blue colouring of the pairs $[\alpha]^2$ has either a red set of order type $\alpha$ or a blue $m$-clique ($K_m$). $\alpha$ is a *partition ordinal* if it has $P_3$ (the "$K_3$" or triangle property). Erdős and Hajnal asked: does $P_3$ imply $P_m$ for every finite $m$? I.e., if $\alpha\to(\alpha,3)^2$, must $\alpha\to(\alpha,m)^2$ hold for all finite $m\geq3$?

Facts

- Status: DISPROVED. Answer: NO. (erdosproblems.com/118, "Status: Disproved"; refutation attributed to Schipperus [Sc99, published as Sc10] and Darby [Da99], independently, c.1999, with Larson supplying a sharpened concrete counterexample.) - Context that made the question natural: Specker (1956) and Chang (1972) proved $\omega^\omega\to(\omega^\omega,3)^2$ (the base case), and Milner (unpublished, written up by Larson, "A short proof of a partition theorem for the ordinal $\omega^\omega$," Ann. Math. Logic 6:129–145, 1973) extended this to $\omega^\omega\to(\omega^\omega,m)^2$ for every finite $m$ — i.e. at $\alpha=\omega^\omega$ specifically, $P_3$ genuinely does propagate to all $P_m$ (arXiv:2011.13218, full text read, §2–3). This positive base case is exactly what made Erdős and Hajnal's general question plausible. - Necessary form (Galvin & Larson, "Pinning countable ordinals," Fund. Math. 82:357–361, 1974/75): any partition ordinal $\alpha>\omega^2$ has the form $\alpha=\omega^{\omega^\beta}$ for some countable $\beta$. All further results are stated for this normal form, using the additive (Cantor) normal form of the exponent $\beta$ — its unique representation as a sum of non-increasing additively-indecomposable ordinals — as the complexity parameter. - Positive result (Schipperus): R. Schipperus, PhD thesis "Countable Partition Ordinals" (Univ. of Colorado, Boulder, 1999, advisor Laver, won the Sacks Prize; published Ann. Pure Appl. Logic 161 (2010) 1195–1215 [Sc10]) — proved every denumerable ordinal $\omega^{\omega^\beta}$ where $\beta$ is (additively indecomposable or) the sum of at most two additively-indecomposable ordinals is a partition ordinal: $\omega^{\omega^\beta}\to(\omega^{\omega^\beta},3)^2$. - Negative results (Darby, Schipperus, sharpened by Larson) — four theorems, increasingly strong, indexed by the number of indecomposable summands of $\beta$ (jal30g.pdf, "1990–2000: A Sampling," verbatim theorem list): 1. (Darby, unpublished) If $\beta=\omega^{\alpha+1}$ and $m\to(4)^3_{232}$ (a finite Ramsey-number condition), then $\omega^{\omega^\beta}\not\to(\omega^{\omega^\beta},m)^2$. 2. (Darby [Da99] and Schipperus [Sc99] independently, for target $K_6$; sharpened to $K_5$ by Larson, "An ordinal partition avoiding pentagrams," J. Symbolic Logic 65(3):969–978, 2000 [La00]) If $\beta=\beta'+\gamma$ with $\beta'\geq\gamma\geq1$ (i.e. $\beta$ a sum of exactly two indecomposables), then $\omega^{\omega^\beta}\not\to(\omega^{\omega^\beta},5)^2$. 3. (Darby [Da99]; Schipperus [Sc99]) If $\beta$ is a sum of three indecomposables, then $\omega^{\omega^\beta}\not\to(\omega^{\omega^\beta},4)^2$. 4. (Schipperus [Sc99]) If $\beta$ is a sum of four (or more) indecomposables, then $\omega^{\omega^\beta}\not\to(\omega^{\omega^\beta},3)^2$ (i.e. $\beta$ with $\geq4$ summands is not even a partition ordinal). - The counterexample that settles #118: take $\beta$ = a sum of *exactly two* additively-indecomposable ordinals. By Schipperus's positive theorem, $\alpha:=\omega^{\omega^\beta}$ has $P_3$ (since $\beta$ is a sum of $\le2$ indecomposables). By theorem (2) above (Darby/Schipperus, sharpened to $K_5$ by Larson 2000), the same $\alpha$ fails $P_5$: $\alpha\not\to(\alpha,5)^2$. Since $\alpha\to(\alpha,m)$ is monotone decreasing in $m$ (a witness for a bigger clique trivially contains one for every smaller clique, so failure at $m$ forces failure at every $m'\geq m$), this single $\alpha$ has $P_3$ but fails $P_m$ for every $m\geq5$. That refutes "$P_3\Rightarrow P_m$ for all finite $m$." - The JSL title "avoiding pentagrams" literally names $K_5$ (a pentagram is the 5-vertex complete graph drawn as a 5-pointed star): Larson's 2000 paper is explicitly engineered to push the Darby/Schipperus obstruction *down* from $K_6$ to $K_5$ — exactly the sharpening needed to land the negative witness inside the zone ($\leq2$ indecomposable summands) where Schipperus's positive $K_3$ theorem already applies, producing the cleanest possible counterexample. - Distinct from the still-open sibling problem: the *general characterization* question "for which countable $\alpha$ does $\alpha\to(\alpha,3)^2$ hold?" (the $\$1000$ Erdős prize problem, Erdős #592 — characterize the countable partition ordinals) remains open — specifically at $\beta$ = sum of exactly three indecomposables, where neither Schipperus's positive machinery (caps at 2 summands) nor a negative $K_3$-failure construction (Schipperus's negative result needs $\geq4$ summands) currently reaches. #118 does *not* need this gap resolved, because its counterexample lives entirely inside the already-settled $\leq2$-summand zone.

Solution

**The transferable idea: locate the exact complexity threshold (here: number of additively-indecomposable Cantor-normal-form summands of the ordinal's exponent) where a positive Ramsey-type existence proof and a negative explicit-coloring construction meet, and engineer the negative construction's *target clique size* down until it lands inside the positive proof's reach.**

1. Identify the right complexity invariant. Both the positive and negative machinery are naturally graded by the same parameter: the number of additively-indecomposable summands in the Cantor normal form of $\beta$, where the ordinal under study is $\omega^{\omega^\beta}$. This invariant governs *both* directions — more summands means more "room" for an adversary to build a bad colouring, but also more structure a positive proof must control. 2. Push the positive proof as far as it goes. Schipperus's positive construction represents the ordinal via finite labelled trees (extending Galvin's notion of a large "free" subset) and proves $K_3$-Ramsey behaviour survives up to $\beta$ = sum of two indecomposables — this is the technique's ceiling; a fully general characterization (all $\beta$) is still open (Erdős #592 — characterize the countable partition ordinals). 3. Push the negative construction's target as low as it goes, independently. Darby's and Schipperus's negative constructions use *weighted-block oscillation colourings*: the ordinal is represented as an interleaving of blocks whose "weights" (drawn from the additive structure of $\beta$'s Cantor normal form) are engineered so that any large homogeneous set is forced into a specific finite combinatorial pattern that provably cannot contain a blue $K_m$ for the chosen $m$ — Darby's method reduces this to a finite combinatorics problem via a careful correspondence between order types of the original ordinal and its candidate large subsets. More indecomposable summands in $\beta$ give the adversary more oscillation freedom, letting $m$ (and even $3$) fail; Larson's 2000 refinement re-examined the same $\beta$ = two-summand construction and found a strictly better colouring witnessing failure already at $K_5$ instead of only $K_6$. 4. Collide the two thresholds. Because Schipperus's positive ceiling ($\leq2$ summands) and Larson's sharpened negative floor ($=2$ summands, $K_5$) meet at the *same* value of the invariant, a single explicit ordinal simultaneously has $P_3$ and lacks $P_5$ (hence lacks $P_m$ for all $m\geq5$) — a clean, fully constructive disproof, with no need to first settle the harder general characterization problem. 5. Why this transfers: whenever a "small case implies all cases" conjecture is built on a base case proved by a powerful but *finitely-reaching* structural technique (tree representations, elementary submodels, interaction schemes — techniques with a known ceiling in some natural complexity grading), look for an independently-constructed adversarial witness graded by the *same* invariant and try to sharpen its target parameter (here, clique size) until the two constructions' thresholds coincide. You do not need to fully map the intermediate territory (the $\beta$=3-summands gap is still open) to get a clean counterexample — you only need the positive and negative constructions to overlap at one point. 6. Separately, Milner/Larson's *positive* extension of $P_3\Rightarrow P_m$ specifically at $\alpha=\omega^\omega$ (the base of the whole hierarchy, $\beta=1$) uses a genuinely different, more powerful toolkit — "interaction schemes" plus the Nash-Williams partition theorem via combinatorial (Galvin–Prikry/Mathias-style) forcing over dense families of finite sets — showing that at the very bottom of the hierarchy the implication *does* hold; it is only once $\beta$ needs $\geq2$ indecomposable summands that this propagation provably breaks. This is itself informative: it shows the "does $K_3$ imply $K_n$" phenomenon is not uniform across the hierarchy, and the Nash-Williams/interaction-scheme toolkit that works at $\beta=1$ has its own ceiling too (it was only carried through for $\omega^\omega$, formalized end-to-end in Isabelle/HOL by Džamonja–Koutsoukou-Argyraki–Paulson, arXiv:2011.13218 — ~4600 lines of formal proof for a 7-page paper, de Bruijn factor ≈23, illustrating how combinatorially dense this toolkit is even at the easiest rung).

Related

- Erdős #590 — ω^ω → (ω^ω, 3)² (Chang's ordinal partition theorem) — the $\beta=1$ (i.e. $\alpha=\omega^\omega$) instance: $P_3$ holds (Chang) and $P_m$ holds for all finite $m$ (Milner/Larson) — the positive base case that motivated #118, fully resolved and formalized (arXiv:2011.13218). - Erdős #591 — is $\omega^{\omega^2}\to(\omega^{\omega^2},3)^2$? — the $\beta=2$-adjacent instance ($\alpha=\omega^{\omega^2}$): resolved positive independently by Schipperus and Darby in the 1990s, using the tree/good-sequence techniques that #118's positive half relies on. - Erdős #592 — characterize the countable partition ordinals — the still-open general characterization question (for which countable $\alpha$ does $\alpha\to(\alpha,3)^2$ hold?), the \$1000 Erdős prize problem; the open frontier is exactly $\beta$ = sum of three indecomposables — a strictly harder question than #118, which #118's counterexample does not need resolved. - Erdős #1169 — ω₁²↛(ω₁²,3)² is solved under CH (Hajnal 1971); ZFC status open — the analogous partition-implication question one cardinal up, at $\omega_1^2$; open in general, true under CH (Hajnal 1971). - Ordinal partition calculus — arrow notation $\\alpha\\to(\\alpha,m)^2$ and the self-partitioning-ordinal program — the general arrow-notation $\alpha\to(\alpha,m)^2$ framework this problem lives in. - Cantor normal form — decomposition of every ordinal into a strictly-decreasing sum of ω^β monomials — the additive-indecomposable-summand decomposition of the ordinal exponent $\beta$ that grades both the positive (Schipperus tree) and negative (Darby/Schipperus block-oscillation) constructions. - concept/nash-williams-partition-theorem — the combinatorial-forcing tool underlying Milner/Larson's positive $\omega^\omega\to(\omega^\omega,m)^2$ extension for all finite $m$ (the base case that made #118 plausible), formalized in Isabelle/HOL (arXiv:2011.13218). - Additively indecomposable ordinals (Cantor's γ-numbers) — the ω^β / Cantor-normal-form-monomial ordinals — the building-block objects ($\beta=\omega^\gamma$) whose sums parametrize the whole positive/negative threshold structure.