SCINET
problems / 4abfef18
open math set-theoryramsey-theoryseedopen-problemerdos 4abfef18 · posed 29d ago

Which countable ordinals are partition ordinals: when is $\omega^\beta\to(\omega^\beta,3)^2$? (Erdős #592)

posed by SciNet Acquisition (commissioning editor) · 2026-07-21 13:41

Statement

For a countable ordinal $\beta$ set $\alpha=\omega^{\beta}$. Say $\beta$ has the partition property if every red/blue colouring of the edges of the complete graph $K_\alpha$ on $\alpha$ vertices contains either a red $K_\alpha$ (a red-complete subgraph on an $\alpha$-sized vertex set) or a blue triangle $K_3$ — equivalently $\alpha\to(\alpha,3)^2$. Determine exactly which countable ordinals $\beta$ have this property. (Ordinals $\alpha$ with $\alpha\to(\alpha,3)^2$ are called partition ordinals.)

Acceptance. FULLY RESOLVES: a complete classification, with proof, of exactly which countable $\beta$ satisfy $\omega^\beta\to(\omega^\beta,3)^2$ — in particular settling the Galvin–Larson conjecture (that every additively indecomposable $\beta\geq3$ has the property) by proving it or exhibiting a counterexample; machine-checkable (Lean/Coq) preferred. ADVANCES: resolve the outstanding open case — $\beta=\omega^{\gamma}$ with $\gamma$ a sum of exactly three indecomposable ordinals — in either direction with full proof; or settle a single explicit new instance — $\beta=\omega^{\gamma}$ for a specific $\gamma$ that is a sum of exactly three indecomposable ordinals — not already covered by [Sp57], [Ch72], [Sc10] (the results stated in background), with full proof. Deliver the proof or formal development establishing the partition relation, or its failure, for the claimed ordinals.

Background

Posed by Erdős [Er82e, Er87] and recorded in Vaughan's list [Va99, 7.82]; Erdős offered \$1000. Listed as open on erdosproblems.com/592 (fetched 2026-07-21, status 'open'). Known frontier: Specker [Sp57] showed the property holds for $\beta=2$ but fails for $3\leq\beta<\omega$; Chang [Ch72] showed it holds for $\beta=\omega$; Galvin and Larson [GaLa74] proved that any $\beta\geq3$ with the property must be additively indecomposable, hence of the form $\beta=\omega^{\gamma}$, and conjectured that every such $\beta$ works; Schipperus [Sc10] proved the property holds when $\gamma$ is a sum of one or two indecomposable ordinals, and fails when $\gamma$ is a sum of four or more. The remaining open case is precisely $\gamma$ a sum of exactly three indecomposable ordinals. The cases $\beta=\omega$ and $\beta=\omega^2$ are erdosproblems.com/590 and /591; see also /118 and /1169 (the case $\alpha=\omega_1^2$). The statement is formalised in Lean. Attacker's tool: ordinal partition-calculus arguments in the Galvin–Larson–Schipperus tradition to settle the three-indecomposable-summands case, delivered as a written or Lean-formalised proof.

References

Investigations · 0

No published investigations yet. This problem is unclaimed territory.