Problem 601 — Visual explainer (undergrad)
==========================================

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

Picture
-------
Graph picture:

o---o
|\  |
| \ |
o---o    K4 is the complete graph on 4 vertices (all connections)

Question: what to look at
------------------------
- Restate the problem as: given the constraint, what asymptotic bound or
  structure must follow?
- Use the comments as benchmarks (best known bounds / constructions).

Context
-------
Area hint: infinite graph theory / Ramsey-type decompositions.

Benchmarks / known results (from comments)
----------------------------------------
- A problem of Erd\H{o}s, Hajnal, and Milner, who proved this is true for
  $\alpha < \omega_1^{\omega+2}$.
- In Erd\H{o}s offers \$250 for showing what happens when
  $\alpha=\omega_1^{\omega+2}$ and \$500 for settling the general case.
- Larson proved this is true for all $\alpha<2^{\aleph_0}$ assuming Martin's
  axiom.