Erdős Problem #601

Erdős Problem 601 --- collection record

PROVENANCE AND STATUS

Saved collaborative-database status: open. Snapshot checked: 2026-09-23T17:22:24Z. Latest status and formalization links: https://teorth.github.io/erdosproblems/

This is an attributed collection of existing writeups. The model-folder names below identify their original attribution; placement in GPT_6_Astra_Ultra does not attribute their mathematical work to that model. All locally available source versions selected for this problem are reproduced below, without editing their text.

Proof claims, computations, literature statements, and completion estimates in the reused text have not been independently verified in this collection pass. A source claiming a solution does not change the saved upstream status.

Primary source (latest numbered version in the preferred model folder): attacks/erdos/gpt_pro_5.2/601.tex.

REUSED SOURCE 1

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

COMPLETION ESTIMATE

Newly verified progress in this collection pass: $0\%$. This measures new verification work, not the amount of mathematics achieved in the reused text.

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