Is $\omega_1^2\not\to(\omega_1^2,k)^2$ provable in ZFC for every finite $k$? (Erdős #1169)
Statement
Write $\alpha\to(\beta,\gamma)^2$ for the partition relation asserting that every $2$-colouring $c:[\alpha]^2\to\{0,1\}$ of the unordered pairs from an ordinal $\alpha$ yields either a $0$-homogeneous subset of order type $\beta$ or a $1$-homogeneous subset of order type $\gamma$; $\not\to$ is its negation. Let $\omega_1^2$ denote the ordinal $\omega_1\cdot\omega_1$. Is it true that, for every finite $k<\omega$, $$\omega_1^2\not\to(\omega_1^2,k)^2\,?$$ The site displays the base case $k=3$: is there a $2$-colouring of $[\omega_1^2]^2$ — equivalently a graph on $\omega_1^2$ whose edges are the $1$-coloured pairs — that is triangle-free (no $1$-homogeneous triple) yet contains no $0$-homogeneous (independent) set of order type $\omega_1^2$?
Acceptance. FULLY RESOLVES: a complete proof — machine-checkable (Lean/Coq) preferred, else a full written proof — that settles the relation in ZFC, i.e. either that $\omega_1^2\not\to(\omega_1^2,k)^2$ holds for every finite $k<\omega$, or that it fails for some finite $k$; OR a proof that the statement is independent of ZFC, exhibiting both a model where it holds (Hajnal's CH model covers one direction) and a forcing/inner model where it fails. ADVANCES (each itself checkable): prove the relation under a hypothesis strictly weaker than the best one currently known to suffice — stated in words, that hypothesis is the continuum hypothesis (Hajnal), so require a strictly weaker set-theoretic assumption with full proof; OR settle a specific finite $k$ outright in ZFC; OR construct a forcing model in which the relation provably fails; OR deliver a Lean/Coq formalization of Hajnal's CH proof. Deliver the proof object or a complete manuscript giving the colouring/forcing construction.
Background
Posed by Erdős and Hajnal and recorded as [Va99,7.85]; listed as open on erdosproblems.com/1169 (fetched 2026-07-21, status 'not disprovable'). The certificate class NOT DISPROVABLE reflects that the relation is known to hold in some models of set theory: Hajnal [Ha71] proved that $\omega_1^2\not\to(\omega_1^2,3)^2$ under the continuum hypothesis. Whether it is a theorem of ZFC, or fails in some model, is open. The partition relation lives on the ordinal $\omega_1^2=\omega_1\cdot\omega_1$, so no finite or countable object witnesses either side — the question concerns uncountable colourings/graphs. A companion problem for countable ordinals is Erdős #592 (erdosproblems.com/592), and a related relation on $\omega_1^2$, whether $\omega_1^2\to(\omega_1\omega,G)^2$ for every $K_4$-free, $K_{\aleph_0,\aleph_0}$-free graph $G$, is Erdős #597 (erdosproblems.com/597), already on this venue. No cash prize was attached. Attacker's tool: forcing and inner-model consistency arguments to separate the relation from ZFC, or a machine-checked (Lean/Coq) formalization of Hajnal's CH-based proof.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #1169 (T. F. Bloom) | website |
| REF-02 | Erdős Problem #592 — related partition problem for countable ordinals | website |
| REF-03 | Erdős Problem #597 — related partition relation on $\omega_1^2$ | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.