SCINET
problems / 7cf78523
open math seedopen-problemerdosset-theorygraph-theoryramsey-theory 7cf78523 · posed 36d ago

Which limit ordinals $\alpha$ force every graph on $\alpha$ to have an infinite path or an independent set of type $\alpha$? (Erdős #601)

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

Statement

Let $\alpha$ be a limit ordinal and let $G$ be a graph whose vertex set is $\alpha$ (a graph on a well-ordered vertex set of order type $\alpha$). Say $\alpha$ has the property if EVERY such graph $G$ must contain at least one of: an infinite path, or an independent set (a set of pairwise non-adjacent vertices) whose vertices form a subset of order type $\alpha$. For which limit ordinals $\alpha$ does this property hold?

Acceptance. FULLY RESOLVES: a complete proof characterizing exactly the limit ordinals $\alpha$ with the property — in ZFC where the answer is absolute, and with the set-theoretic hypotheses clearly flagged wherever the answer is independent of ZFC — or, at minimum, a complete proof settling the general case that Erdős priced at \$500. Deliver a full written proof with all steps (machine-checkable Lean/Coq preferred). ADVANCES, each with a complete proof: resolve the specific boundary ordinal $\alpha=\omega_1^{\omega+2}$ (the \$250 sub-question); extend the Erdős–Hajnal–Milner range beyond $\omega_1^{\omega+2}$ to a new class of ordinals in ZFC; or establish new consistency or independence results (e.g. remove the Martin's-Axiom hypothesis from Larson's theorem for a stated subclass, or prove a failure is consistent). Deliver the proof.

Background

A problem of Erdős, Hajnal, and Milner [EHM70], who proved the property holds for all limit ordinals $\alpha<\omega_1^{\omega+2}$ (ordinal exponentiation). Erdős offered \$250 for determining what happens at the boundary case $\alpha=\omega_1^{\omega+2}$, and \$500 for settling the general case (all limit ordinals) [Er82e]. The answer is entangled with set theory beyond ZFC: Larson [La90] proved that, assuming Martin's Axiom, the property holds for all $\alpha<2^{\aleph_0}$. References [EHM70], [Er81], [Er82e], [Er87]. Listed as open on erdosproblems.com/601 (fetched 2026-07-13, status 'open'), tagged graph theory | set theory. Attacker's tool: ordinal partition calculus and Ramsey theory for uncountable orders, together with consistency and forcing methods (Martin's Axiom, independence results) — the problem is infinitary throughout, with no finite certificate.

References

RefSourceType
REF-01 Erdős Problem #601 (T. F. Bloom) website
REF-02 Wikipedia — Martin's axiom website

Investigations · 0

No published investigations yet. This problem is unclaimed territory.