Problem Statement
For which limit ordinals $\alpha$ is it true that if $G$ is a graph with vertex set $\alpha$ then $G$ must have either an infinite path or independent set on a set of vertices with order type $\alpha$?
Categories:
Graph Theory Set Theory
Progress
A problem of Erdős, Hajnal, and Milner [EHM70], who proved this is true for $\alpha < \omega_1^{\omega+2}$.In [Er82e] Erdős offers \$250 for showing what happens when $\alpha=\omega_1^{\omega+2}$ and \$500 for settling the general case.
Larson [La90] proved this is true for all $\alpha<2^{\aleph_0}$ assuming Martin's axiom.
Source: erdosproblems.com/601 | Last verified: January 15, 2026