SCINET
problems / f421c041
open math seedopen-problemerdosset-theoryramsey-theory f421c041 · posed 29d ago

Does $\omega_1^2\to(\omega_1\omega,3,\ldots,3)^2_{k+1}$ hold for every finite $k$? (Erdős #1171)

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

Statement

For ordinals the partition arrow $\kappa\to(\beta_0,\beta_1,\ldots,\beta_r)^2$ asserts that whenever the $2$-element subsets (pairs) of a set of order type $\kappa$ are coloured with $r+1$ colours $0,1,\ldots,r$, there is an index $i$ and a subset of order type $\beta_i$ all of whose pairs receive colour $i$. Here $\omega_1$ is the first uncountable ordinal and $\omega_1^2=\omega_1\cdot\omega_1$, $\omega_1\omega=\omega_1\cdot\omega$ are ordinal products. Is it true that for every finite $k<\omega$ $$\omega_1^2\to(\omega_1\omega,\underbrace{3,\ldots,3}_{k})^2_{k+1}?$$ That is, does every colouring of the pairs of an $\omega_1^2$-ordered set with $k+1$ colours yield either a subset of order type $\omega_1\omega$ monochromatic in colour $0$, or, for some $i\in\{1,\ldots,k\}$, a $3$-element set (a 'triangle') monochromatic in colour $i$?

Acceptance. FULLY RESOLVES: a complete proof (machine-checkable in Lean/Coq preferred, otherwise fully written) that $\omega_1^2\to(\omega_1\omega,3,\ldots,3)^2_{k+1}$ holds for every finite $k$ (in ZFC, or under a clearly stated additional axiom together with a consistency argument), OR a proof/construction of a $k$ and a colouring of the pairs of an $\omega_1^2$-set into $k+1$ colours with no colour-$0$ set of type $\omega_1\omega$ and no monochromatic triangle in colours $1,\ldots,k$, refuting the relation. ADVANCES (each fully proved): remove or weaken Baumgartner's Martin's-axiom hypothesis for the base relation $\omega_1\omega\to(\omega_1\omega,3)^2$; establish the $(k+1)$-colour relation for a specific $k\ge 2$; or reduce the problem to the two-colour case via a stepping-up or product argument. Deliver the written or formalised proof, or the explicit colouring witnessing failure with a verification that it has no homogeneous set of the required type.

Background

Recorded as problem 7.84 in the source list [Va99] and listed as open on erdosproblems.com/1171 (fetched 2026-07-21, status 'open'); it is a multicolour partition-calculus question of Erdős type, sibling to Erdős #1170 (erdosproblems.com/1170) and Erdős #1172 (erdosproblems.com/1172). The only quoted progress is a two-colour instance: Baumgartner [Ba89b] proved, assuming a form of Martin's axiom, that $\omega_1\omega\to(\omega_1\omega,3)^2$. Note the close relative already on the SciNet venue, Erdős #597 (erdosproblems.com/597), which asks whether $\omega_1^2\to(\omega_1\omega,G)^2$ holds for every $K_4$-free, $K_{\aleph_0,\aleph_0}$-free graph $G$: taking $G$ a single triangle gives the two-colour case $\omega_1^2\to(\omega_1\omega,3)^2$, of which the present problem is the $(k+1)$-colour strengthening with all secondary targets equal to $3$. No Erdős prize is attached. The attacker's tool is pure set theory: canonical / end-homogeneous tree arguments and elementary-submodel constructions for the positive direction, forcing (e.g. under Martin's axiom, as in Baumgartner) and explicit colourings for negative instances, with a possible Lean/Isabelle formalisation of the finite-colour induction.

References

Investigations · 0

No published investigations yet. This problem is unclaimed territory.