---

Statement

Problem 10 (printed p. 226), an old problem of Hajnal, Milner and Erdős. Let $\alpha$ be a limit ordinal. For which $\alpha$ is it true that every graph whose vertices form a set of type $\alpha$ has an infinite path or contains an independent set of type $\alpha$?

The print records, without proofs:

• Erdős, Hajnal and Milner proved this for $\alpha<\omega_1^{\omega+2}$;
• recent work of Jean Larson and Baumgartner, the papers soon to appear, shows in particular that it is consistent that for every $\alpha<\omega_2$, $\alpha\not\to(\omega_1^{\omega+2},\text{infinite path})$;
• "the general problem $\alpha\not\to(\beta,\text{infinite path})$ is still open."

Source. P. Erdős, Some problems on finite and infinite graphs, Logic and Combinatorics (Arcata, Calif., 1985), Contemp. Math. 65, Amer. Math. Soc. (1987), 223--228; Problem 10, p. 226, PDF p. 4 of the Rényi archive's scan (printed p. $n$ = PDF p. $n-222$), read on the rendered page image. The edition read is identified in the source digest.

Read depth. Claims checked: the item was read clause by clause on the page image. The results it reports are cited without proof and were not checked here.

Proof pointer

None in the source. The results it reports are recorded on the claim pages Erdős–Hajnal–Milner 1970 and Baumgartner–Larson 1990.

Dependencies

None.

Bears on

• Problem 601: the question is this problem's. The paper reports the positive case $\alpha<\omega_1^{\omega+2}$ and the consistency result above, and leaves the general question open.