Problem 601

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$ ?

Source: erdosproblems.com/601

Graph theory
Set theory

Wiki page

Status

Open

No claim settles this problem.

Open. The site labels the problem OPEN and credits [EHM70] with every limit $\alpha<\omega_1^{\omega+2}$ and [La90] with every limit $\alpha<2^{\aleph_0}$ under Martin's axiom. The site's commentary records Erdős's offers in [Er82e] of a prize for the case $\alpha=\omega_1^{\omega+2}$ and a larger one for the general question.

EHM70: Erdős, P. and Hajnal, A. and Milner, E. C., Set mappings and polarized partition relations. Combinatorial theory and its applications, I-III (Proc. Colloq., Balatonfüred, 1969) (1970), 327-363.
Er82e: Erdős, Paul, Some of my favourite problems which recently have been solved. (1982), 59-79.
La90: Larson, Jean A., Martin's axiom and ordinal graphs: large independent sets or infinite paths. Ann. Pure Appl. Logic (1990), 31-39.
BL90: Baumgartner, James E. and Larson, Jean A., A diamond example of an ordinal graph with no infinite paths. Ann. Pure Appl. Logic 47 (1990), 1-10. Not on the site's list.
La86: Larson, Jean A., A consequence of no short scale for ordinal graphs with no infinite paths. J. London Math. Soc. (2) 33 (1986), 193-202. Not on the site's list.
La87: Larson, Jean A., A GCH example of an ordinal graph with no infinite path. Trans. Amer. Math. Soc. 303 (1987), 383-393. Not on the site's list.

Problem 601

Status

Proof claims

Discussion