gpt pro 5.2 attempt on Math-869

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

1) FORMAL RESTATEMENT

Let $\alpha$ be a limit ordinal. Consider any simple undirected graph $G=(\alpha,E)$ on vertex set $\alpha$.

An infinite path means a sequence of distinct vertices $(v_n)_{n<\omega}$ such that $\{v_n,v_{n+1}\}\in E$ for all $n$.

An independent set of order type $\alpha$ means a subset $I\subseteq\alpha$ such that

1. no two distinct elements of $I$ are adjacent in $G$ (i.e., $[I]^2\cap E=\emptyset$), and
2. the well-order induced from $\alpha$ on $I$ has order type exactly $\alpha$.

Question: classify the limit ordinals $\alpha$ such that every graph on vertex set $\alpha$ has either an infinite path or an independent set of order type $\alpha$.

2) QUICK LITERATURE/CONTEXT CHECK

The statement records: Erdős--Hajnal--Milner proved the property for all $\alpha<\omega_1^{\omega+2}$; Larson proved it for all $\alpha<2^{\aleph_0}$ assuming Martin's axiom. I do not import additional results.

3) ATTACK PLAN

• Proof-track idea: attempt induction on $\alpha$ using ordinal decompositions (Cantor normal form) and show that rayless graphs force large independent sets aligned with the ordinal structure.
• Disproof-track idea: build a rayless graph on $\alpha$ that blocks independent sets of order type $\alpha$ by inserting dense "obstacles" in each interval of $\alpha$.
• Sanity check: verify the statement for the smallest limit ordinal $\alpha=\omega$ by a direct argument.

4) WORK

Fast reality check: $\alpha=\omega$. For graphs on $\omega$, "independent set of order type $\omega$" is the same as "infinite independent set". We show every graph on $\omega$ has either an infinite path or an infinite independent set.

Lemma 601.1 (countable infinite Ramsey step).
Let $G$ be a graph on vertex set $\omega$. Then $G$ contains either an infinite clique or an infinite independent set.

Proof. We build inductively an increasing sequence of vertices $v_0<v_1<\cdots$ and a nested sequence of infinite sets \[ V_0\supseteq V_1\supseteq V_2\supseteq\cdots\subseteq\omega \] with $v_n\in V_n$ and such that for each $n$, all vertices in $V_{n+1}$ are either all adjacent to $v_n$ or all non-adjacent to $v_n$.

Start with $V_0:=\omega$. Given $V_n$ infinite, let $v_n$ be its least element. Let \[ N_n := \{w\in V_n\setminus\{v_n\}: \{v_n,w\}\in E(G)\} \] be the set of neighbours of $v_n$ inside $V_n\setminus\{v_n\}$. Either $N_n$ is infinite or its complement in $V_n\setminus\{v_n\}$ is infinite. Define $V_{n+1}$ to be an infinite subset of $N_n$ if $N_n$ is infinite, otherwise an infinite subset of $(V_n\setminus\{v_n\})\setminus N_n$. This completes the recursion.

Now define a label $\varepsilon_n\in\{0,1\}$ by $\varepsilon_n=1$ if $V_{n+1}\subseteq N_n$ (we chose neighbours) and $\varepsilon_n=0$ otherwise (we chose non-neighbours). Since the sequence $(\varepsilon_n)$ takes only two values, there exists an infinite set of indices $I\subseteq\omega$ such that $\varepsilon_n$ is constant on $I$. Let $\{n_0<n_1<\cdots\}$ enumerate $I$ and consider the vertex set $S:=\{v_{n_k}:k<\omega\}$.

If $\varepsilon_n=1$ for all $n\in I$, then for $k<l$ we have $v_{n_l}\in V_{n_k+1}\subseteq N_{n_k}$, so $\{v_{n_k},v_{n_l}\}\in E(G)$. Hence $S$ is an infinite clique.

If $\varepsilon_n=0$ for all $n\in I$, then for $k<l$ we have $v_{n_l}\in V_{n_k+1}$ and $V_{n_k+1}$ consists of non-neighbours of $v_{n_k}$, so $\{v_{n_k},v_{n_l}\}\notin E(G)$. Hence $S$ is an infinite independent set.

Thus $G$ has an infinite clique or an infinite independent set. $\square$

Lemma 601.2 (infinite clique $\Rightarrow$ infinite path).
Let $G$ be a graph on a vertex set that is well-ordered (in particular on an ordinal). If $G$ contains an infinite clique, then $G$ contains an infinite path.

Proof. Let $C$ be an infinite clique. Choose a countably infinite subset $\{c_0,c_1,c_2,\dots\}\subseteq C$ of distinct vertices. Reorder them so that $c_0<c_1<c_2<\cdots$ in the ambient well-order. Since $C$ is a clique, every pair is adjacent; in particular $\{c_n,c_{n+1}\}\in E(G)$ for all $n$. Therefore $(c_n)_{n<\omega}$ is an infinite path. $\square$

Corollary 601.3 ($\alpha=\omega$ case).
Every graph on vertex set $\omega$ contains either an infinite path or an independent set of order type $\omega$.

Proof. Apply Lemma 601.1. If we get an infinite independent set, we are done. If we get an infinite clique, apply Lemma 601.2 to obtain an infinite path. $\square$

5) VERIFICATION

• Lemma 601.1 is self-contained and uses only infinite pigeonhole (that among infinitely many $\varepsilon_n\in\{0,1\}$ one value occurs infinitely often).
• Lemma 601.2 is straightforward: in a clique, consecutive vertices of any infinite sequence form edges.
• The corollary matches examples: the infinite star has an infinite independent set (the leaves); an infinite complete graph has an infinite path.

6) FINAL

UNRESOLVED

(i) Strongest proved partial result. The statement holds for $\alpha=\omega$ (Corollary 601.3), via Lemmas 601.1--601.2.

(ii) First gap (crisp). For $\alpha>\omega$, determine whether there exists a rayless graph on vertex set $\alpha$ with no independent set of order type $\alpha$; equivalently, extend the direct arguments beyond $\omega$ without importing the deep results cited in the problem text.

(iii) Top 3 next moves.

1. Try to generalize Lemma 601.1 to longer ordinals by building sequences indexed by $\alpha$ and extracting homogeneous subsequences using cofinality arguments.
2. For candidate counterexamples at $\alpha=\omega_1^{\omega+2}$, attempt to construct graphs with a rank decomposition that blocks independent sets cofinal in each "level" while keeping the graph rayless.
3. Computation/sanity: for small countable ordinals (e.g., $\omega^2$), attempt to construct explicit graphs (by hand) that are rayless and inspect the order types of maximal independent sets.

(iv) What a minimal counterexample would look like. A minimal counterexample at a limit ordinal $\alpha$ would be a graph $G$ on vertex set $\alpha$ such that:

1. $G$ has no infinite path (rayless),
2. every independent set $I\subseteq\alpha$ has order type $<\alpha$.