Erdős #591 — is $\omega^{\omega^2}\to(\omega^{\omega^2},3)^2$?

Statement

Let $\alpha=\omega^{\omega^2}$. Is it true that in any red/blue colouring of the edges of the complete graph $K_\alpha$ (vertex set the ordinal $\alpha$) there is either a red $K_\alpha$ (a subset of order type $\alpha$ all of whose edges are red) or a blue $K_3$ (a monochromatic blue triangle)? Equivalently, using Rado's arrow notation, is $\alpha\to(\alpha,3)^2$?

Erdős posed this ($250 prize) as the natural next test case above $\omega^\omega$ in his and Hajnal's general question: characterize the countable ordinals $\alpha$ with $\alpha\to(\alpha,3)^2$ (the general question is Erdős #592 — characterize the countable partition ordinals).

Facts

- Status: SOLVED, affirmative. Answer: yes, $\omega^{\omega^2}\to(\omega^{\omega^2},3)^2$. Marked "PROVED" on erdosproblems.com/591 (fetched 2026-07-02); prize \$250. - Origin: Erdős, "Some of my favourite problems which recently have been solved" (1982) [Er82e]; "Some problems on finite and infinite graphs" (1987) [Er87]; "Some of Paul's favorite problems" booklet (1999), item 7.82 [Va99]; the general form of the conjecture is due to Erdős and Hajnal, *Unsolved problems in set theory* (1971). - Context/comparison (from erdosproblems.com/591): Specker [Sp57] proved the analogous relation holds at $\alpha=\omega^2$ and fails at $\alpha=\omega^n$ for every finite $n$ with $3\le n<\omega$. Chang [Ch72] proved it holds at $\alpha=\omega^\omega$ — that is Erdős #590 — ω^ω → (ω^ω, 3)² (Chang's ordinal partition theorem). #591 is the *next* rung up: $\alpha=\omega^{\omega^2}$. - Only powers of $\omega$ can possibly work at all. If $\alpha$ is not a power of $\omega$ it is additively decomposable, $\alpha=\beta+\gamma$ with $\beta,\gamma<\alpha$; colouring pairs $0$ if both endpoints lie in $\beta$ or both in $[\beta,\beta+\gamma)$ and $1$ otherwise gives a 2-colouring with no monochromatic-blue triangle and no red copy of $\alpha$ — Galvin's observation (reproduced as Observation 2.2 in arXiv:2011.13218), refined by Galvin & Larson [GaLa74] to show any working $\alpha\ge\omega^3$ must actually be $\omega^\beta$ for $\beta$ itself a power of $\omega$... this pruning is why attention concentrates on $\alpha=\omega^{\omega^\beta}$. - Who solved it, and the exact scope of the theorem it falls under: Rene Schipperus, PhD thesis (Univ. Calgary, 1999), published as "Countable partition ordinals," *Ann. Pure Appl. Logic* 161 (2010) 1195–1215 [Sc10], proved the general positive theorem: *if $\beta<\omega_1$'s Cantor Normal Form has at most two (additively-indecomposable) summands, then $\omega^{\omega^\beta}\to(\omega^{\omega^\beta},3)^2$.* Independently, Carl Darby is credited by erdosproblems.com with an independent proof of the same $\beta=2$ instance (Darby's confirmed published paper, "Negative partition relations for ordinals $\omega^{\omega^\alpha}$," *J. Comb. Theory Ser. B* 76 (1999) 205–222, is on the negative side of the surrounding dichotomy — see caveat in provenance). - #591 is precisely the case $\beta=2$: since $2=1+1$ is a sum of two additively-indecomposable ordinals (namely $1+1$), it falls under Schipperus's $\le 2$-summand theorem. - Sharpness — the result cannot be pushed to bigger monochromatic-blue targets at this level. Schipperus [Sc10] and (independently) Larson (unpublished, "An ordinal partition avoiding pentagrams") showed that for $\beta$ a sum of *two* indecomposables (in particular $\beta=2$), $\omega^{\omega^\beta}\not\to(\omega^{\omega^\beta},5)^2$ — i.e. one cannot upgrade blue-$K_3$ to blue-$K_5$ at this ordinal. This negative companion result for the *same* ordinal $\omega^{\omega^2}$ is Does the K3 partition-ordinal property imply the Kn property? (Erdős–Hajnal, disproved by Darby/Schipperus/Larson) territory (the general question of whether the $K_3$-property implies the $K_n$-property for all finite $n$: no). - The full picture one level up ($\alpha=\omega^{\omega^\beta}$, varying the number of indecomposable summands of $\beta$) is exactly Erdős #592 — characterize the countable partition ordinals: $\le 2$ summands → positive [Sc10]; $=3$ summands → open (this is the current frontier); $\ge 4$ summands → negative even for $m=3$ [Sc10]. #591 sits at the safely-positive end of this dichotomy ($\beta=2$, two summands). - Formalization status: the Isabelle/HOL project of Džamonja, Koutsoukou-Argyraki & Paulson (arXiv:2011.13218, *Experimental Mathematics* 31:2 (2022) 383–400) machine-verified the *one-exponential-level-lower* case $\omega^\omega\to(\omega^\omega,m)^2$ for all finite $m$ (Milner's unpublished strengthening of Chang, via Larson's proof) — i.e. it formalizes Erdős #590 — ω^ω → (ω^ω, 3)² (Chang's ordinal partition theorem), not #591 itself. No formalization of Schipperus's/Darby's proof of #591 was found as of this search (2026-07-02). - A sketch of Schipperus's proof, in 7 parts, is given in the Hajnal–Larson survey chapter of the *Handbook of Set Theory*, pp. 188–209 (per WebSearch cross-check of the Schipperus 2010 abstract's citation trail; full text paywalled, not independently re-derived here). The multi-decade gap between the 1999 thesis and 2010 journal publication is itself cited (by the Isabelle/HOL paper's authors) as evidence of how delicate the correctness-checking of this argument was.

Solution

Answer: yes, $\omega^{\omega^2}\to(\omega^{\omega^2},3)^2$.

The transferable technique — "climb the tower one indecomposable summand at a time" via canonical (Nash-Williams-style) colourings:

1. *Base engine (Specker → Chang → Milner → Larson, the machinery formalized for Erdős #590 — ω^ω → (ω^ω, 3)² (Chang's ordinal partition theorem) in arXiv:2011.13218).* At the ground level $\omega^\omega$ ($\beta=1$), the positive relation is proved not by a direct Ramsey argument on pairs, but by first *canonicalizing* an arbitrary 2-colouring of pairs into finitely many "interaction-scheme forms" using ordinary Ramsey's theorem on an auxiliary infinite index set, and then applying the Nash-Williams partition theorem — a genuine strengthening of Ramsey's theorem from colourings of $k$-element sets to colourings of *thin (Nash-Williams) families* of finite subsets of $\omega$ (families where no member is an initial segment of another) — to extract a homogeneous set of the target order type. This two-stage "canonicalize, then apply a front/tree Ramsey theorem" pattern is the reusable engine. 2. *Necessary-condition pruning (Galvin).* Before attacking any specific $\alpha$, a one-line adversary colouring (split $\alpha=\beta+\gamma$, colour by "same side / different side") kills every $\alpha$ that is not a power of $\omega$, and a refinement (Galvin–Larson [GaLa74]) further forces attention onto $\alpha=\omega^{\omega^\beta}$. This "cheap necessary condition via an explicit adversary 2-colouring" is itself a reusable move: it converts an apparently wide search space (all countable ordinals) into a one-parameter family ($\beta$) before any hard construction begins. 3. *Schipperus's extension (the actual new idea that cracked #591 and the general $\le2$-summand case).* Schipperus's thesis/paper generalizes the $\beta=1$ machinery one full exponential level up by inducting on the number of additively-indecomposable summands in the Cantor Normal Form of $\beta$ itself (not of $\alpha$): each indecomposable piece of $\beta$ contributes a "copy" of the ground-level ($\omega^\omega$-style) canonical-partition argument, and the pieces are then combined — via a further tree/interaction-scheme bookkeeping layer built on top of Nash-Williams — so that the *whole* colouring of $K_{\omega^{\omega^\beta}}$ is forced into a canonical form controlled by finitely many parameters per summand. The induction closes cleanly for one or two summands (giving #591's $\beta=2$ case, and Chang's $\beta=1$ case as the base of the induction) but the combinatorial bookkeeping becomes unmanageable/actually fails for three or more summands — for $\ge4$ summands Schipperus himself found an explicit adversary colouring showing the relation is simply *false*, and the exact 3-summand boundary is the open heart of Erdős #592 — characterize the countable partition ordinals. 4. *Why this is the "idea to borrow":* the pattern — (a) find a cheap necessary condition that collapses the search space to a single Cantor-Normal-Form parameter, (b) build a base-case canonical-colouring engine (Ramsey/Nash-Williams + interaction schemes), (c) induct that engine one indecomposable summand at a time — is exactly the tool any attack on the open $3$-summand case of Erdős #592 — characterize the countable partition ordinals would need to either extend (to close the positive side) or diagnose precisely where it breaks (to build the matching negative-side adversary colouring, as was done for $\ge4$ summands).

Related

- Erdős #590 — ω^ω → (ω^ω, 3)² (Chang's ordinal partition theorem) — the $\beta=1$ instance ($\omega^\omega\to(\omega^\omega,3)^2$, in fact $\to(\omega^\omega,m)^2$ for all finite $m$), the base case of Schipperus's induction; proved by Chang/Milner/Larson and machine-formalized in Isabelle/HOL (arXiv:2011.13218) - Erdős #592 — characterize the countable partition ordinals — the general characterization of countable partition ordinals $\omega^{\omega^\beta}$ by number of indecomposable summands of $\beta$; #591 is exactly the resolved $\beta=2$ (two-summand) case, the open frontier is $\beta$ = sum of exactly three indecomposables - Does the K3 partition-ordinal property imply the Kn property? (Erdős–Hajnal, disproved by Darby/Schipperus/Larson) — whether the $K_3$-partition property implies the $K_n$-property for all finite $n$: no, via the same Schipperus/Larson negative construction that shows $\omega^{\omega^2}\not\to(\omega^{\omega^2},5)^2$ - Ordinal partition calculus — arrow notation $\\alpha\\to(\\alpha,m)^2$ and the self-partitioning-ordinal program — the $\alpha\to(\beta,\gamma)^r$ arrow-notation framework (Rado) this problem lives in - Cantor normal form — decomposition of every ordinal into a strictly-decreasing sum of ω^β monomials — the decomposition of $\beta$ into additively-indecomposable summands that indexes the whole Schipperus dichotomy - Additively indecomposable ordinals (Cantor's γ-numbers) — the ω^β / Cantor-normal-form-monomial ordinals — the necessary structural class (Galvin, Galvin–Larson) any candidate exponent must belong to - concept/nash-williams-partition-theorem — the thin-family generalization of Ramsey's theorem underlying the Specker/Chang/Milner/Larson base engine that Schipperus's proof extends - Machine formalization of infinitary combinatorics proofs (Isabelle/HOL, Lean) — arXiv:2011.13218's Isabelle/HOL verification of the one-level-lower ($\beta=1$) case; a template/prerequisite library a future formalization of #591 itself could build on