Erdoes #601 - working report - Erdős Problem a Day

Erdős problem 601 — live check, literature audit, and a finite-kernel reduction

Access date: 2026-07-28 UTC.

Claim labels used throughout:

[a] elementary-rigorous: proved from definitions in this report.
[b: theorem/source] rigorous modulo named theorem: the deduction is rigorous assuming the explicitly named standard theorem or cited paper.
[c] plausible/structural-unverified: a proposed route or an honest negative search result, not a theorem.
[d] computational-only: established only for the finite instances checked by the accompanying program.

0. Mandatory live-page check — done before mathematics

[a] Live status. I fetched <https://www.erdosproblems.com/601> through the Bright Data browser on 2026-07-28. The page says OPEN - $500. It displays:

0 comments on this problem;
0 claimed proofs for this problem;
Interested in collaborating None;
Currently working on this problem None;
Formalised statement? No;
all of the other activity markers (“likes”, “looks difficult”, “looks

tractable”, and formalisation activity) as None.

Thus the mandatory stop condition is not triggered.

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

[a] Verbatim page remarks/known results. The LaTeX view at <https://www.erdosproblems.com/latex/601> says:

A problem of Erd\H{o}s, Hajnal, and Milner \cite{EHM70}, who proved this is true for $\alpha < \omega_1^{\omega+2}$.
In \cite{Er82e} Erd\H{o}s offers \$250 for showing what happens when $\alpha=\omega_1^{\omega+2}$ and \$500 for settling the general case.
Larson \cite{La90} proved this is true for all $\alpha<2^{\aleph_0}$ assuming Martin's axiom.

[a] References actually exposed by the live page. The header lists [EHM70][Er81][Er82e][Er87]; the prose additionally links [La90]. Opening the page's bibliography widget gave:

[EHM70] P. Erdős, A. Hajnal, E. C. Milner, *Set mappings and polarized

partition relations*, Combinatorial Theory and its Applications I–III (1970), 327–363, MR 299537.

[Er81] P. Erdős, *On the combinatorial problems which I would most like to

see solved*, Combinatorica (1981), 25–42, MR 602413.

[Er82e] P. Erdős, *Some of my favourite problems which recently have been

solved* (1982), 59–79, MR 690096.

[Er87] P. Erdős, Some problems on finite and infinite graphs, in *Logic

and Combinatorics* (1987), 223–228, MR 891250.

[La90] J. A. Larson, *Martin's axiom and ordinal graphs: large independent

sets or infinite paths*, Ann. Pure Appl. Logic 47 (1990), 31–39, DOI 10.1016/0168-0072(90)90015-T.

No comment, proof claim, or worker was hidden behind the displayed counters.

1. What the question means

Write

P(\alpha):\quad \text{every graph on the well-order }\alpha\text{ has a ray or an independent subset of order type }\alpha .

Here a ray is a sequence of distinct vertices $(v_n)_{n<\omega}$ with $v_nv_{n+1}$ an edge for every $n$.

[a] Equivalent rayless formulation. $P(\alpha)$ says exactly that every rayless graph on $\alpha$ has an independent subset of order type $\alpha$. This elementary reformulation will be used below.

2. Primary-literature audit

I searched the exact title/relation, the three old paper titles, arXiv, and forward citations of the Larson and Baumgartner–Larson papers. Discovery metadata were checked against the primary papers or publisher pages before a mathematical claim was used.

2.1 Results verified in primary sources

[b: EHM70, Theorem 7.] The scan of the original paper is available from the Erdős archive at <https://users.renyi.hu/~p_erdos/1970-19.pdf>. Theorem 7 says that a graph on an ordered set of type $\theta<\omega_1^{\omega+2}$, with no infinite path, has an independent set of the same type. The paper explicitly says that the bound enters through its set-mapping theorem and that the authors could not prove the graph statement for arbitrary $\theta$.

[a] Original prize wording checked. The original Er82e scan is <https://users.renyi.hu/~p_erdos/1982-33.pdf>. Problem 42 gives the non-monotone infinite-path formulation, says the proof breaks down at $\omega_1^{\omega+2}$, and records the \$250/\$500 offers. Thus the website's transcription is supported by the original source.

[b: Larson 1990.] Larson's publisher page, <https://www.sciencedirect.com/science/article/pii/016800729090015T>, states that Martin's axiom extends the positive relation to every limit ordinal below $2^{\aleph_0}$. The DOI, volume, year, and page range agree with the live page.

[b: Baumgartner–Larson 1990.] The primary publisher abstract, <https://www.sciencedirect.com/science/article/pii/016800729090013R>, states that Jensen's diamond is used to construct counterexamples for

\omega_1^{\omega+2}\leq\alpha<\omega_2.

The paper is J. E. Baumgartner and J. A. Larson, A diamond example of an ordinal graph with no infinite paths, Ann. Pure Appl. Logic 47 (1990), 1–10, DOI 10.1016/0168-0072(90)90013-R. This important negative result is not currently mentioned in the prose of the live #601 page.

[b: Larson 1987.] Larson's A GCH example of an ordinal graph with no infinite path, Trans. AMS 303 (1987), 383–393, DOI 10.1090/S0002-9947-1987-0896028-6, constructs, under GCH, counterexamples cofinally among ordinals of each finite higher cardinality $\aleph_n$, $n\geq2$. This was checked against the primary-paper text indexed from the AMS article, not inferred from its title.

[b: Larson 2006.] The abstract of Partition relations on a plain product order type, Ann. Pure Appl. Logic 144 (2006), 117–125, <https://www.sciencedirect.com/science/article/pii/S0168007206000613>, explicitly encourages work on whether CH decides the path relation for $\omega^*\!\cdot\omega_1$ and for $\omega_1^{\omega+2}$. This identifies the sharp first well-ordered frontier, rather than merely saying “the general case is difficult.”

[b: Garti 2023.] S. Garti, Tiltan and graphs with no infinite paths, arXiv:2302.09492, published as DOI 10.1007/s10998-023-00544-3, concerns the non-well-order $\omega^*\!\cdot\omega_1$. It proves a consistency result for that type and reproduces a useful finite-kernel lemma. It does not settle the well-ordered case $\omega_1^{\omega+2}$.

2.2 A necessary interpretation of “open”

Let

\alpha_0=\omega_1^{\omega+2}.

[b: Baumgartner–Larson + Larson + standard forcing consistency.] The truth of $P(\alpha_0)$ is already relatively independent of ZFC:

in $L$, diamond holds, so Baumgartner–Larson give

$\neg P(\alpha_0)$;

in a model of $\mathrm{MA}+2^{\aleph_0}=\omega_2$, one has

$\alpha_0<\omega_2=2^{\aleph_0}$, so Larson gives $P(\alpha_0)$.

The second comparison uses only that $\alpha_0$ has cardinality $\aleph_1$, hence is below the initial ordinal $\omega_2$. Consequently, no axiom-free list assigning an absolute yes/no value to every limit ordinal can exist.

[c] Honest current-state search result. I found no primary source after Larson 2006 that decides whether CH alone decides $P(\alpha_0)$. The 2023 Garti paper and the 2025 Garti–Shelah superclub paper discuss the parallel type $\omega^*\!\cdot\omega_1$, not a resolution of the well-ordered $\alpha_0$ case. This is a report of the searches performed, not a proof that no such paper exists. The live page's present OPEN status is consistent with this literature picture.

3. A from-scratch finite-kernel normal form

The following reduction is the main rigorous output of this run. It makes the obstruction at $\alpha_0$ concrete.

3.1 The thinning lemma

Lemma 1 [b: infinite Ramsey theorem]. Let $G=(V,E)$ be rayless and let $C\subseteq V$ be countably infinite. There are a finite set $A\subseteq V$ and an infinite $B\subseteq C$ such that

$B$ is independent;
every $a\in A$ is adjacent to every $b\in B$;
every $v\in V\setminus A$ has at most one neighbour in $B$.

This is also Lemma 2.2 of Garti 2023, but here is an independent proof.

Proof. By infinite Ramsey, $C$ has an infinite homogeneous subset. It cannot be a clique, since a countably infinite clique contains a ray, so take an infinite independent $D_0\subseteq C$.

Starting with $D_0$, try recursively to choose distinct vertices $a_i$ and infinite sets

D_{i+1}=D_i\cap N(a_i)

whenever a new $a_i$ has infinitely many neighbours in $D_i$. If this continued forever, choose

d_i\in D_{i+2}\setminus\{d_j:j<i\}.

Then

a_0,d_0,a_1,d_1,a_2,d_2,\ldots

would be a ray. Hence the process stops after some finite $\ell$. Put $A=\{a_i:i<\ell\}$ and $D=D_\ell$. The nesting makes every member of $A$ complete to $D$, while stopping says that every vertex outside $A$ has only finitely many neighbours in $D$. Also $A\cap D_0$ is empty, because $D_0$ is independent.

Colour a pair $\{x,y\}\in[D]^2$ with colour 0 if some $v\notin A$ is adjacent to both, and colour 1 otherwise. Apply infinite Ramsey again. An infinite colour-0 set would yield a ray: recursively choose its vertices $b_0,b_1,\ldots$, and a common neighbour $v_i\notin A$ of $b_i,b_{i+1}$, choosing $b_{i+1}$ outside the finitely many neighbours of all earlier $v_j$. Then

b_0,v_0,b_1,v_1,b_2,v_2,\ldots

is a ray. Therefore the homogeneous set $B$ has colour 1. It has all three asserted properties. $\square$

3.2 Normal form for every limit ordinal

[a] Ordinal block decomposition. Every nonzero limit ordinal has a unique form

\alpha=\omega\beta.

Its consecutive blocks

C_\xi=[\omega\xi,\omega(\xi+1))\qquad(\xi<\beta)

all have type $\omega$.

Theorem 2 (finite-kernel normal form) [b: Lemma 1]. For every rayless graph $G$ on a limit ordinal $\alpha=\omega\beta$, there is an induced subgraph $H$ of order type $\alpha$, partitioned as

V(H)=\bigcup_{\xi<\beta}B_\xi,

and finite sets $K_\xi\subseteq V(H)$ such that:

$B_\xi\subseteq C_\xi$ has type $\omega$ and is independent;
$K_\xi\cap B_\xi=\varnothing$, and every member of $K_\xi$ is

complete to $B_\xi$;

every $v\in V(H)\setminus K_\xi$ has at most one neighbour in

$B_\xi$.

Proof. Apply Lemma 1 independently to every $C_\xi$, obtaining $(A_\xi,B_\xi)$. Let $H$ be induced by $\bigcup_{\xi<\beta}B_\xi$ and put $K_\xi=A_\xi\cap V(H)$. The construction in Lemma 1 has $A_\xi\cap B_\xi=\varnothing$. All three local properties follow from the lemma. Finally,

\operatorname{otp}V(H)=\sum_{\xi<\beta}\operatorname{otp}(B_\xi) =\sum_{\xi<\beta}\omega=\omega\beta=\alpha.

$\square$

[a] Exactness of the reduction. Therefore $P(\alpha)$ is equivalent to its restriction to rayless graphs in the finite-kernel normal form of Theorem 2. One implication is restriction; for the other, reduce an arbitrary rayless graph to the full-order-type induced $H$.

3.3 The kernel-incidence restriction

Define a finite set mapping on the block indices by

F(\xi)=\{\eta<\beta:K_\xi\cap B_\eta\ne\varnothing\}.

Lemma 3 [a]. $F(\xi)$ is finite, $\xi\notin F(\xi)$, and the directed graph with arcs $\xi\to\eta$ for $\eta\in F(\xi)$ has no directed ray.

Proof. Finiteness and the missing loop follow from Theorem 2. If $\xi_0\to\xi_1\to\cdots$ were a directed ray, choose

a_n\in K_{\xi_n}\cap B_{\xi_{n+1}}.

Now $a_{n-1}\in B_{\xi_n}$, while $a_n\in K_{\xi_n}$ is complete to $B_{\xi_n}$. Thus $a_{n-1}a_n$ is an edge for every $n\ge1$, and the disjointness of the blocks makes the $a_n$'s distinct. They form a ray in $H$, contradiction. $\square$

[a] Clean-column consequence. If $J\subseteq\beta$ is $F$-free, meaning

\xi,\eta\in J\Longrightarrow \eta\notin F(\xi),

then in $H_J=H[\bigcup_{\xi\in J}B_\xi]$, every vertex has at most one neighbour in each column. If additionally $\operatorname{otp}(J)=\beta$, then $H_J$ still has type $\alpha$.

This reduces the first obstruction to a precise restricted set-mapping question:

Kernel-free-set subproblem. Must every finite set mapping $F:\beta\to[\beta]^{<\omega}$ that arises as above (in particular, has no directed ray) have an $F$-free subset of order type $\beta$?

[c] Proving this at $\beta=\omega_1^{\omega+2}$, or showing exactly which additional incidence restriction from Theorem 2 is needed, would remove the first obstruction in this normal-form route. The unrestricted finite set-mapping theorem used by EHM is known to fail at its boundary, so silently applying that theorem at equality would be invalid.

4. The clean-column forcing reduction

Let $\mathbb P(H)$ be the set of finite independent subsets of a rayless graph $H$, ordered by reverse inclusion (a stronger condition contains more vertices).

Lemma 4 [b: Δ-system lemma and infinite Ramsey theorem]. $\mathbb P(H)$ is ccc.

Proof. If there were an uncountable antichain, the Δ-system lemma and finite thinning would give conditions $p_i$ with the same root and pairwise disjoint petals of one fixed size $k>0$. Enumerate the $i$-th petal as

x_i^0,\ldots,x_i^{k-1}.

For each $i<j$, incompatibility must be witnessed by an edge between the two petals; an edge involving the common root would already violate the independence of one condition. Colour $\{i,j\}$ by one witnessing pair $(r,s)$. Infinite Ramsey gives an infinite set on which the same pair $(r,s)$ works.

If $r=s$, the vertices $x_i^r$ form an infinite clique and hence a ray. If $r\ne s$, relabel the homogeneous indices by the natural numbers. The sequence

x_0^r,\ x_2^s,\ x_1^r,\ x_3^s,\ x_2^r,\ x_4^s,\ x_3^r,\ldots

is a ray: every required edge has the form $x_i^r x_j^s$ with $i<j$, and no vertex repeats. Both cases contradict raylessness. $\square$

Now suppose the columns are clean, so all $K_\xi$'s are empty. For $\xi<\beta$ and $n<\omega$, define

D_{\xi,n}=\{p\in\mathbb P(H):|p\cap B_\xi|\ge n\}.

Lemma 5 [a]. Every $D_{\xi,n}$ is dense.

Proof. Given finite $p$, each member of $p$ forbids at most one vertex of the infinite independent column $B_\xi$. Hence finitely many additional compatible vertices of $B_\xi$ can be added. $\square$

[a] Filter-to-independent-set conversion. If a filter meets all $D_{\xi,n}$, its union is independent and meets every $B_\xi$ infinitely. For a set $J$ of columns of type $\beta$, this union has order type $\omega\beta=\alpha$.

[b: Martin's axiom]. For a clean graph with only $<2^{\aleph_0}$ such dense requirements, MA supplies the filter. This is the transparent forcing mechanism behind the positive side; it is not a ZFC construction of the filter.

[a] Why the finite kernels are real, not cosmetic. In the full normal form, $D_{\xi,1}$ is not dense below a condition containing a member of $K_\xi$, because that kernel vertex is adjacent to every point of $B_\xi$. Conversely, below a condition disjoint from $K_\xi$, the same finite-forbidden-set proof works. Thus the two exact tasks are:

avoid the finite kernel incidences on a set of columns of full order

type; and

meet the resulting column-density requirements.

At $\alpha_0=\omega_1^{\omega+2}$, there are $\aleph_1$ requirements. MA with a larger continuum meets them; CH by itself gives no such generic filter. Diamond can organize a counterexample.

[c] Precise wall. A result at the CH frontier must therefore do one of the following:

prove under CH that every finite-kernel normal form admits a full-order

kernel-free selection and the required filter (possibly in one combined construction);

build a CH counterexample without using diamond; or
construct, relatively consistently, a CH model in which all such normal

forms have the desired independent set.

This is a set-theoretic uniformity/forcing problem, not a missing finite search. No number of finite graph CPU-hours can distinguish the two already-known forcing models.

5. Exact finite clean-column theorem

There is nevertheless a sharp, fully checked finite shadow of Lemma 5. Let $Q(b,m)$ mean:

every graph split into $b$ independent columns of $m$ vertices, with each vertex having at most one neighbour in every other column, has an independent transversal (one vertex from each column).

Theorem 6 [a].

Q(b,m)\quad\Longleftrightarrow\quad b\le m \qquad(b,m\ge1).

Proof. If $b\le m$, process the columns in order. Before column $j$ there are $j<b\le m$ selected vertices. Each forbids at most one of its $m$ candidates, so at least one candidate remains.

If $b>m$, label the vertices in every column by $0,\ldots,m-1$, and join vertices in distinct columns exactly when their labels agree. This is a clean graph consisting of $m$ disjoint copies of $K_b$. An independent transversal would assign distinct labels to all $b$ columns, impossible by the pigeonhole principle. $\square$

[a] Unbounded kernel size. There is no uniform finite bound hidden in Lemma 1. In $K_{r,\aleph_0}$, take $C$ to be the infinite side. The graph is rayless: a simple path uses at most the $r$ vertices on the finite side. For any infinite $B\subseteq C$, all $r$ finite-side vertices must belong to $A$, since otherwise one of them has infinitely many neighbours in $B$. Thus the least possible kernel size can be arbitrarily large.

6. Standalone re-verification

The checker is erdos601_wavew001_reverify.py. It uses only the Python standard library.

Run:

python3 runs/erdos601_wavew001_reverify.py

The central clean-graph construction and transversal search are:

def graph_from_pair_matchings(b, m, pair_matchings):
    adj = [0] * (b * m)
    for (ci, cj), matching in zip(combinations(range(b), 2), pair_matchings):
        for ri, rj in enumerate(matching):
            if rj >= 0:
                u, v = ci * m + ri, cj * m + rj
                adj[u] |= 1 << v
                adj[v] |= 1 << u
    return adj

def find_transversal(adj, b, m):
    chosen = []
    def rec(column, chosen_mask):
        if column == b:
            return True
        for row in range(m):
            v = column * m + row
            if not (adj[v] & chosen_mask):
                chosen.append(v)
                if rec(column + 1, chosen_mask | (1 << v)):
                    return True
                chosen.pop()
        return False
    return tuple(chosen) if rec(0, 0) else None

SHA-256 at the time of this report:

4dc77563e1f97656a0a72c3a48a5e1135e3fddeb01fed2ecc678d08da27e3899

[d] Exhaustive output. The program enumerates every allowed matching between every pair of columns in the following tractable cells:

 b  m  pair-matchings searched  universal transversal
 1  1                        1  YES
 1  2                        1  YES
 1  3                        1  YES
 2  1                        2  NO
 2  2                        7  YES
 2  3                       34  YES
 3  1                        2  NO
 3  2                      229  NO
 3  3                    39304  YES
 4  1                        2  NO
 4  2                      229  NO

For negative cells it stops at the first counterexample; for positive cells it exhausts the entire cell and also runs the proof's greedy algorithm.

[d] Additional independent checks. The same run:

verifies the $m$ disjoint $K_b$ obstruction for

$1\le b\le7$, $1\le m\le6$;

mechanically checks the two explicit homogeneous-grid path templates in

Lemma 4 for 4 through 12 petals;

brute-forces the minimum kernel size $r$ in the finite witnesses

$K_{r,8}$, for $1\le r\le8$.

The final output was ALL CHECKS PASSED; measured runtime was 0.47 seconds and maximum resident set size was 11,512 KB. These computations verify the finite claims and proof templates only; they are not promoted to an uncountable theorem.

7. Bottom line

[a] This run does not close #601. It does provide an exact full-order-type finite-kernel normal form for every limit ordinal, proves the associated finite-independent-set forcing is ccc, identifies the kernel-incidence map as a finite directed-rayless set mapping, and proves the sharp finite clean-column threshold $b\le m$.

[b: Baumgartner–Larson and Larson] The primary literature shows that the first boundary value is model-dependent. [c] The CH case singled out by Larson remains the precise literature wall found in this search.

PARTIAL: Every rayless instance reduces rigorously to a full-type finite-kernel column graph with a ccc finite-independent-set poset; the remaining CH-frontier obstruction is the full-order kernel avoidance plus an aleph_1-sized dense-set selection, and the exact finite clean analogue is Q(b,m) iff b<=m.

This is the AI working report, labelled by outcome — not an independently verified claim unless marked PROVED. ← ledger