Erdős #592 — characterize the countable partition ordinals

Statement

Determine which countable ordinals $\beta$ have the property that, if $\alpha=\omega^\beta$, then in any red/blue colouring of the edges of $K_\alpha$ there is either a red $K_\alpha$ or a blue $K_3$. Equivalently: characterize the countable ordinals $\beta$ such that $\alpha \to (\alpha,3)^2$ where $\alpha=\omega^\beta$. Such $\alpha$ are called partition ordinals.

Facts

- Prize \$1000; status OPEN, "cannot be resolved with a finite computation" (erdosproblems.com/592, site-owner belief, verified by direct fetch 2026-07-02). - Falsifiable: no — this is a full characterization question over all countable ordinals $\beta<\omega_1$, not a single yes/no with a finite witness; a complete answer needs a genuine proof (and even a partial answer, e.g. resolving one more $\beta$, needs a proof, not a computation). - Origin: Erdős, "Some of my favourite problems which recently have been solved" (1982) [Er82e]; Erdős, "Some problems on finite and infinite graphs" (1987) [Er87]; "Some of Paul's favorite problems" booklet, Budapest 1999, item 7.82 [Va99]. - Known results / best bounds (all from erdosproblems.com/592 remarks, cross-checked against the linked bib entries): - Specker [Sp57] (*Teilmengen von Mengen mit Relationen*, Comment. Math. Helv. 1957): $\beta=2$ works; $3\leq\beta<\omega$ fails. - Chang [Ch72] (*A partition theorem for the complete graph on $\omega^\omega$*, J. Combin. Theory Ser. A 1972, sciencedirect.com/science/article/pii/0097316572901057): $\beta=\omega$ works, i.e. $\omega^\omega\to(\omega^\omega,3)^2$. E.C. Milner (unpublished) extended this to $\omega^\omega\to(\omega^\omega,m)^2$ for every finite $m$, and this stronger statement together with a full proof chain (Erdős-Milner, Specker, Larson, Nash-Williams) was machine-formalized in Isabelle/HOL by Džamonja, Koutsoukou-Argyraki & Paulson, arXiv:2011.13218 (Experimental Mathematics 31:2 (2022) 383-400) — the first (and so far only, per this search) formal-proof-assistant verification of any result in this specific family. - Galvin & Larson [GaLa74] (*Pinning countable ordinals*, Fund. Math. 1974/75): if $\beta\geq3$ has the partition-ordinal property then $\beta$ must be additively indecomposable, hence $\beta=\omega^\gamma$ for some countable ordinal $\gamma$. They conjecture every additively-indecomposable $\beta\geq3$ of this form has the property — this conjecture is the effective open core of #592, and per the Lean formalization (google-deepmind/formal-conjectures/.../592.lean, # TODO(firsching): add condition by Galvin and Larson) it has not even been encoded as a sub-statement yet, only the raw characterization question. - Schipperus [Sc10] (*Countable partition ordinals*, Ann. Pure Appl. Logic 161 (2010) 1195-1215, sciencedirect.com/science/article/pii/S0168007209002188): for $\beta=\omega^\gamma$, the property holds if $\gamma$ is the sum of one or two additively-indecomposable ordinals, and fails if $\gamma$ is the sum of four or more. The proof (per the erdosproblems.com remark and the Hajnal-Larson Handbook-of-Set-Theory survey chapter, which the search confirmed contains a 7-part, ~20-page sketch of it) constructs, for the positive direction, explicit large near-homogeneous structures built from the additively-indecomposable summands, and for $\gamma\geq4$-indecomposable-summands, an explicit counterexample colouring (in the 1990s, Darby and Schipperus independently found families of counterexamples for these "MI" — multiply-indecomposable — ordinals; Larson later improved one of their constructions, e.g. showing $\alpha=\omega^{\omega^2}\not\to(\alpha,5)^2$ [La00]). The remaining open case is exactly $\gamma$ = the sum of three additively-indecomposable ordinals — this is the frontier of #592. - The specific instance $\beta=\omega$ (i.e. $\gamma=1$) is Erdős #590 — ω^ω → (ω^ω, 3)² (Chang's ordinal partition theorem) (resolved, Chang); $\beta=\omega^2$ (i.e. $\gamma=2$, one indecomposable summand at the next level up — resolved by Schipperus/Darby) is Erdős #591 — is $\omega^{\omega^2}\to(\omega^{\omega^2},3)^2$?. Does the K3 partition-ordinal property imply the Kn property? (Erdős–Hajnal, disproved by Darby/Schipperus/Larson) is the closely related (and resolved-in-the-negative) question of whether the $K_3$ property implies the $K_n$ property for all finite $n$ — answer no, via the same Schipperus/Darby counterexample machinery. Erdős #1169 — ω₁²↛(ω₁²,3)² is solved under CH (Hajnal 1971); ZFC status open is the analogous question one cardinal up, at $\omega_1^2$, open in general but true under CH (Hajnal [Ha71]). - Formalized: statement yes, proof no. FormalConjectures/ErdosProblems/592.lean (google-deepmind/formal-conjectures, fetched 2026-07-02) states erdos_592 as an iff against an answer(sorry) placeholder — pure statement scaffold, no partial machinery, and explicitly flags the Galvin-Larson necessary condition as not-yet-encoded. - Related problems: Erdős #590 — ω^ω → (ω^ω, 3)² (Chang's ordinal partition theorem), Erdős #591 — is $\omega^{\omega^2}\to(\omega^{\omega^2},3)^2$?, Does the K3 partition-ordinal property imply the Kn property? (Erdős–Hajnal, disproved by Darby/Schipperus/Larson), Erdős #1169 — ω₁²↛(ω₁²,3)² is solved under CH (Hajnal 1971); ZFC status open (all linked directly from the erdosproblems.com "See also" on this and neighboring pages, verified by direct fetch).

Literature state

Not resolved, and the erdosproblems.com page's own framing plus the 2010 Schipperus paper together pin down exactly where the frontier is: the property is known to hold for $\beta=\omega^\gamma$ when $\gamma$ is additively decomposable into $\leq2$ indecomposable pieces, known to fail for $\geq4$ pieces, and the case of exactly 3 indecomposable summands is open — this is very likely the single hardest remaining sub-case referenced implicitly by the "OPEN" status. I found no paper post-dating Schipperus 2010 that resolves the 3-summand case; the most recent directly-adjacent work located is arXiv:2604.23433 (Duman, Gönül, Kaya, Saxena, Tamer, submitted 25 Apr 2026, "On closed Ramsey numbers of small countable ordinals") which improves bounds on closed ordinal Ramsey numbers $R^{cl}(\omega\cdot n+1,3)$ and proves a new necessary condition for being a "topological partition ordinal" — a stronger/different (closed-coloring) variant of the same underlying combinatorics, not a resolution of #592's ordinary-colouring question, but evidence the surrounding research area (ordinal partition calculus for pairs) is still active as of mid-2026. No AI/LLM/automated-theorem-prover resolution was found; the only AI-adjacent artifact is the DeepMind formal-conjectures Lean *statement* (unproved) and the unrelated Isabelle/HOL *formalization of the already-solved* $\beta=\omega$ case (arXiv:2011.13218) — i.e. AI/formalization effort so far has only re-verified old results, not extended them. The Galvin-Larson conjecture itself (every additively-indecomposable $\beta\geq3$ has the property) remains fully open as a conjecture — Schipperus's 1-or-2-summand vs. $\geq4$-summand dichotomy neither proves nor disproves it in general.

Attack surface

- Mode: literature-resolution (confirm no post-2010 paper closes the 3-indecomposable-summand gap; track arXiv:2604.23433's authors and citations forward) + derivation+formalization (the problem is explicitly non-finite; any progress must extend Schipperus's or a genuinely new combinatorial/tree/topological-Ramsey-space argument to the 3-summand case, or exhibit a new counterexample construction in that case analogous to Darby/Schipperus's $\geq4$-summand construction). - Concrete first experiment: not a computation (falsifiability: not-finite). The realistic first move is (1) obtain and closely read the Schipperus 2010 paper (Ann. Pure Appl. Logic, sciencedirect.com/science/article/pii/S0168007209002188) and the Hajnal-Larson Handbook survey's 7-part proof sketch to identify precisely why the counterexample construction (for $\geq4$ indecomposable summands) breaks down at exactly 3, and why the positive construction (for $\leq2$) doesn't extend to 3 — that structural gap is the actual mathematical content to attack; (2) check whether the closed-Ramsey-number machinery of arXiv:2604.23433 (topological partition ordinals, necessary conditions of the form $\omega^\theta\nrightarrow_{cl}(\omega^\alpha,3)^2$ when $\theta<R(\alpha,3)$) can be adapted from the closed-colouring setting to the ordinary-colouring setting of #592, since it is the most recent (Apr 2026) active machinery in the same "small countable ordinal partition relation" family. - Oracle: none mechanical for the general characterization (it is a $\Pi$-style statement over all countable $\beta$); for the specific open sub-case (3 indecomposable summands) the oracle is a human/formal proof, verifiable in principle by encoding into the Lean FormalConjectures/ErdosProblems/592.lean scaffold or the Isabelle/HOL ordinal-partition library already built by Paulson et al. (arXiv:2011.13218) for the $\beta=\omega$ case, which supplies reusable formalized machinery (Erdős-Milner, Specker, Larson, Nash-Williams lemmas) that a 3-summand proof could plausibly be built on top of and then machine-checked. - Feasibility: honest read: famous-and-hard, not in reach for a finite-search or SAT-style attack. This is a genuine infinite-combinatorics/set-theory research problem at the level of a $1000 Erdős prize with a 45+ year history (1974 Galvin-Larson conjecture, 2010 Schipperus partial resolution, no progress found since). The one concretely promising, non-speculative thread is the freshly (Apr 2026) active closed-ordinal-Ramsey-number line (arXiv:2604.23433) — worth monitoring/citation-tracking rather than attacking directly, since it is the only sign of live research momentum in this exact neighborhood.

Related

- Erdős #590 — ω^ω → (ω^ω, 3)² (Chang's ordinal partition theorem) — the $\beta=\omega$ (i.e. $\gamma=1$) instance, resolved by Chang [Ch72]; formalized in Isabelle/HOL (arXiv:2011.13218) - Erdős #591 — is $\omega^{\omega^2}\to(\omega^{\omega^2},3)^2$? — the $\beta=\omega^2$ (i.e. $\gamma=2$) instance, resolved by Schipperus/Darby independently [Sc10] - Does the K3 partition-ordinal property imply the Kn property? (Erdős–Hajnal, disproved by Darby/Schipperus/Larson) — resolved-negative: the $K_3$-partition-ordinal property does not imply the $K_n$ property for all finite $n$ (same Schipperus/Darby counterexample family) - Erdős #1169 — ω₁²↛(ω₁²,3)² is solved under CH (Hajnal 1971); ZFC status open — analogous partition question one cardinal up, at $\omega_1^2$; open in general, true under CH [Ha71] - 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 - Additively indecomposable ordinals (Cantor's γ-numbers) — the ω^β / Cantor-normal-form-monomial ordinals — the necessary structural condition (Galvin-Larson) any candidate $\beta$ must satisfy - Cantor normal form — decomposition of every ordinal into a strictly-decreasing sum of ω^β monomials — how $\gamma$ decomposes into a sum of indecomposable ordinals, the axis along which Schipperus's dichotomy (1-2 vs. $\geq4$ summands) is stated - Closed ordinal Ramsey numbers $R^{cl}(\\alpha,3)$ — the topological (closed-in-supremum) variant of ordinal partition calculus — the $R^{cl}$ variant studied by the most recent (2026) adjacent paper, arXiv:2604.23433 - Topological Ramsey spaces / Nash-Williams tree-front machinery — the general machinery (Nash-Williams-style trees/fronts) underlying Chang/Schipperus-type positive partition results and their Isabelle/HOL formalization - Machine formalization of infinitary combinatorics proofs (Isabelle/HOL, Lean) — arXiv:2011.13218's Isabelle/HOL verification of the already-solved $\beta=\omega$ case; a template for how a future 3-summand proof could be machine-checked