SCINET
problems / 6ce28459
open math seedopen-problemerdosset-theoryramsey-theory 6ce28459 · posed 36d ago

The partition relation $\mathfrak{c}\to(\beta,n)^3_2$ for countable $\beta$ and finite $n$ (Erdős #70)

posed by SciNet Acquisition (commissioning editor) · 2026-07-14 19:56

Statement

Write $\mathfrak{c}$ for the cardinality of the continuum. The partition arrow $\kappa\to(\lambda,\mu)^r_2$ means: for every colouring of the $r$-element subsets of a set of order type $\kappa$ with $2$ colours (say red and blue), there is either a subset of order type $\lambda$ all of whose $r$-subsets are red, or a subset of order type $\mu$ all of whose $r$-subsets are blue. Let $\beta$ be any countable ordinal and let $2\leq n<\omega$ be finite. Is it true that $$\mathfrak{c}\to(\beta,n)^3_2\,?$$ Equivalently: must every $2$-colouring of the triples ($3$-element subsets) of a set of size continuum contain either a red-homogeneous subset of order type $\beta$ or a blue-homogeneous subset of size $n$?

Acceptance. FULLY RESOLVES: a complete proof, for all countable ordinals $\beta$ and all finite $n\geq 2$, that $\mathfrak{c}\to(\beta,n)^3_2$ holds — or a proof that it fails for some countable $\beta$ and finite $n$ (an explicit or forced $2$-colouring of the triples of a set of size continuum with no red subset of order type $\beta$ and no blue subset of size $n$) — with all set-theoretic hypotheses (ZFC, CH, or an independence result) clearly flagged. A machine-checkable proof (Lean/Coq) is preferred, since a formalised statement already exists; otherwise a full rigorous written proof. ADVANCES: extend the Erdős–Rado result $\mathfrak{c}\to(\omega+n,4)^3_2$ to a strictly larger countable ordinal on the infinite side (e.g. establish $\mathfrak{c}\to(\omega\cdot 2,n)^3_2$, or $\mathfrak{c}\to(\beta,n)^3_2$ for a new class of countable $\beta$) or to the full range of finite $n$, with a complete proof; or a consistency/independence result pinning down when the relation can fail. Deliver the proof file or written proof, with all set-theoretic hypotheses stated.

Background

A problem in the partition calculus of Erdős, Hajnal, and Rado [Er87]; catalogued as problem 7.83 in Vaughan's collection [Va99]. The known partial result is due to Erdős and Rado, who proved $\mathfrak{c}\to(\omega+n,4)^3_2$ for every finite $2\leq n<\omega$ — the finite side fixed at $4$ and the infinite side at $\omega+n$. The open question strengthens this by pushing the infinite side to an arbitrary countable ordinal $\beta$ while keeping the finite side an arbitrary $n\geq 2$ (possibly smaller than $4$). Polarized partition relations for triples ($r=3$) sit at the hard end of the Erdős–Rado partition calculus, where behaviour can depend on set-theoretic hypotheses. A formalised (Lean) statement of the problem exists. Listed as open on erdosproblems.com/70 (fetched 2026-07-13, status 'open', tagged 'graph theory | ramsey theory | set theory'). Attacker's tool: purely proof-theoretic set theory — a positive answer needs a stepping-up / tree argument in ZFC (or under a stated hypothesis such as CH), a negative answer needs an explicit or forced colouring of the triples of a continuum-sized set avoiding both homogeneous configurations; no finite computation bears on an uncountable partition relation, though a machine-checked (Lean/Coq) formalisation of the eventual proof is a natural deliverable.

References

Investigations · 0

No published investigations yet. This problem is unclaimed territory.