Erdős Problem #591

Erdős Problem #591: the ordinal $\omega^{\omega^2}$

A block gluing theorem and a precise obstruction, 24 September 2026.

Statement and corrected literature status

The question is whether $\alpha\to(\alpha,3)^2$ for $\alpha=\omega^{\omega^2}$, with the red copy required to preserve order type. The older local attempt treated this as open. The current page records the positive solution of Schipperus and Darby. Schipperus's primary abstract states that $\omega^{\omega^\beta}\to(\omega^{\omega^\beta},3)^2$ when $\beta$ is the sum of one or two indecomposable ordinals; here $\beta=2=1+1$ qualifies. We do not substitute this citation for a reconstructed general proof. The work below isolates and proves a block case.

A finite-partition fact

For every countable ordinal $\gamma$, any finite partition of $\omega^\gamma$ has a class of order type $\omega^\gamma$. Here is a transfinite induction. The case $\gamma=0$ is a singleton. For $\gamma=\delta+1$, divide into $\omega$ consecutive blocks of type $\omega^\delta$, apply induction inside each, and take infinitely many blocks selecting the same class. For a nonzero countable limit $\gamma$, choose strictly increasing $\gamma_j$ cofinal in $\gamma$ and divide into blocks of type $\omega^{\gamma_j}$. Again one class occurs on an infinite subsequence; its union has type $\omega^\gamma$, because those exponents are cofinal. The equality of the ordinal sum with $\omega^\gamma$ follows from continuity of ordinal exponentiation and its upper bound by the ambient ordinal. In particular, any proper finite coloring of a blue graph on $\omega^{\omega j}$ has a color class which is a red clique of that entire order type.

A complete block-uniform case

Decompose \[\alpha=\sum_{j=1}^{\infty}\omega^{\omega j} \] into consecutive blocks $I_j$. Suppose the edge coloring has these two extra properties: the blue graph inside each $I_j$ has finite chromatic number (the bound may depend on $j$), and all edges between any fixed pair $I_i,I_j$ have one common color. Assume that there is no blue triangle.

Color the pair $\{i,j\}$ by that common interblock color. This quotient coloring on $\mathbb N$ also has no blue triangle: choosing one vertex from each of three such blocks would otherwise give one upstairs. It therefore has an infinite red set of indices $J$. To justify this last elementary assertion, if a chosen index has infinitely many blue neighbors they form an infinite red clique; otherwise repeatedly remove its finite blue neighborhood and continue in its infinite red neighborhood.

Within each $I_j$, $j\in J$, apply the finite-partition fact to a proper finite blue coloring. Obtain a red clique $R_j$ of type $\omega^{\omega j}$. Every cross edge between these selected cliques is red by the quotient choice. Since $J$ is unbounded in $\mathbb N$, \[\operatorname{otp}\left(\bigcup_{j\in J}R_j\right) =\sum_{j\in J}\omega^{\omega j}=\omega^{\omega^2}. \] This proves the original conclusion for this precise class of colorings, including cases with no uniform finite bound on the chromatic numbers of the individual blocks.

Why separate large red blocks cannot simply be joined

Take two consecutive blocks of any infinite order type $\lambda$. Color within each block red and every cross edge blue. There is no blue triangle, since among three vertices two lie in one block. Both blocks are red copies of $\lambda$, but no red clique meets both. Thus the mere existence of many individually large red pieces is not a gluing argument. The uniform quotient and an infinite red set of indices are what justify the union in the preceding proof. In a general coloring, the cross edges between two blocks need not be uniform. Also, the induced blue graphs inside the blocks can have infinite chromatic number. Neither difficulty is removed by the finite-partition lemma. The old local restriction to an initial segment of type $\omega^\omega$ is valid relative to Chang's theorem, but likewise does not resolve either obstacle.

Outcome and remaining gap

Attempt status: unresolved. The transfinite finite-partition lemma and the stated block gluing theorem are proved. Arbitrary edge colorings on $\alpha$ are not handled; their structural analysis is the substantial missing part of the known solution. No new resolution or local formal verification is claimed. Sources: https://www.erdosproblems.com/591; R. Schipperus, Countable partition ordinals, Ann. Pure Appl. Logic 161 $2010$, 1195--1215, primary abstract https://doi.org/10.1016/j.apal.2009.12.007.

COMPLETION ESTIMATE

COMPLETION: 30%

Let $\alpha$ be the infinite ordinal $\omega^{\omega^2}$. Is it true that in any red/blue colouring of the edges of $K_\alpha$ there is either a red $K_\alpha$ or a blue $K_3$? For comparison, Specker [Sp57] proved this property holds when $\alpha=\omega^2$ and false when $\alpha=\omega^n$ for $3\leq n<\omega$. Chang proved this property holds when $\alpha=\omega^\omega$ (see [590] ). See [592] for the general case. References [Sp57] Specker, Ernst, Teilmengen von Mengen mit Relationen . Comment. Math. Helv. $1957$, 302-314.

FORMAL RESTATEMENT

Fix the ordinal $\alpha := \omega^{\omega^2}$. Let $[\alpha]^2 := \{\{x,y\}: x,y<\alpha,\ x\neq y\}$. A  red/blue edge-colouring is a map $c:[\alpha]^2\to\{\text{red},\text{blue}\}$. Write $K_\alpha$ for the complete graph on vertex set $\alpha$ with edge-set $[\alpha]^2$.

A  red $K_\alpha$ means: there exists a subset $X\subseteq \alpha$ such that $1$ $(X,<)$ is order-isomorphic to $(\alpha,<)$ (so $X$ has order-type $\alpha$), and $2$ for all distinct $x,y\in X$, $c(\{x,y\})=\text{red}$.

A  blue $K_3$ means: there exist $x<y<z<\alpha$ with $c(\{x,y\})=c(\{x,z\})=c(\{y,z\})=\text{blue}$.

Question: Is it true that every $c:[\alpha]^2\to\{\text{red},\text{blue}\}$ produces either a red $K_\alpha$ or a blue $K_3$? (Equivalently: does $\alpha\to(\alpha,3)^2$ hold for $\alpha=\omega^{\omega^2}$?)

QUICK LITERATURE/CONTEXT CHECK

I will not import any external results beyond what is explicitly stated in the problem text. The text states: the property holds for $\alpha=\omega^2$ (Specker), fails for $\alpha=\omega^n$ for $3\le n<\omega$ (Specker), and holds for $\alpha=\omega^\omega$ (Chang). The present case $\alpha=\omega^{\omega^2}$ is presented as open.

ATTACK PLAN

Proof-track ideas.

• (Inductive block construction) Use the Cantor normal form structure of $\omega^{\omega^2}=\sup_{m<\omega}\omega^{\omega\cdot m}$ and try to build a red copy by iterating a "build a red $\omega^{\omega\cdot(m+1)}$ from many red $\omega^{\omega\cdot m}$" step under the hypothesis "no blue triangle".
• (Canonical/closure argument) Attempt to define, for each vertex, a large red-closed set using the triangle-free-blue constraint and then perform transfinite recursion to obtain a red set of the desired order-type.

Disproof-track ideas.

• (Specker-style colouring) Try to generalize the known counterexamples for $\omega^n$ ($n\ge 3$) by defining a blue triangle-free graph on $\omega^{\omega^2}$ whose red edges avoid a red copy of $\omega^{\omega^2}$.
• (Block-diagonal construction) Decompose $\omega^{\omega^2}$ into $\omega$ many intervals and define colors by relative positions so that every large-order-type subset picks up enough blue edges to prevent being all red, yet without creating a blue triangle.

I did not succeed in either direction. Below are rigorous partial lemmas and sanity checks.

WORK

FAST REALITY CHECK (finite and simplest infinite cases)

• Finite analogue fails quickly: a brute-force check over all $2^6$ red/blue colourings of the edges of $K_4$ finds counterexamples. For instance, colour a single edge blue and all other edges red. Then there is no blue triangle (only one blue edge) and there is no red $K_4$ (since not all edges are red). So "$4\to(4,3)^2$" is false.
• For $\alpha=\omega$ the analogue does hold: any red/blue coloring of $K_\omega$ contains either an infinite red clique (hence a red $K_\omega$) or a blue triangle. A full proof is given as Lemma lem:omega_case.

Lemma 1 (blue neighborhood is a red clique). Let $\alpha$ be any ordinal and let $c:[\alpha]^2\to\{\text{red},\text{blue}\}$ be a colouring with no blue triangle. For any vertex $v<\alpha$, define the blue neighborhood \[ N_{\text{blue}}(v):=\{u<\alpha: u\neq v\text{ and }c(\{u,v\})=\text{blue}\}. \] Then every edge inside $N_{\text{blue}}(v)$ is red; i.e. for all distinct $u,w\in N_{\text{blue}}(v)$ we have $c(\{u,w\})=\text{red}$.

Proof. Fix $v$ and take distinct $u,w\in N_{\text{blue}}(v)$. By definition $c(\{u,v\})=c(\{w,v\})=\text{blue}$. If $c(\{u,w\})=\text{blue}$ also held, then $\{u,v,w\}$ would be a blue $K_3$, contradicting the hypothesis. Therefore $c(\{u,w\})=\text{red}$. Since $u,w$ were arbitrary, all edges inside $N_{\text{blue}}(v)$ are red.$\square$

Lemma 2 (the $\omega$ case, constructive). Let $c:[\omega]^2\to\{\text{red},\text{blue}\}$ be a colouring with no blue triangle. Then there exists an infinite increasing sequence $(x_n)_{n<\omega}$ of naturals such that every edge $\{x_i,x_j\}$ ($i<j$) is red. Equivalently, $K_\omega$ contains a red $K_\omega$.

Proof. We build recursively an increasing sequence $x_0<x_1<x_2<\cdots$ together with infinite sets $A_n\subseteq\omega$ satisfying:

1. $x_n=\min(A_n)$,
2. $A_{n+1}\subseteq A_n\setminus\{x_n\}$,
3. for every $m\le n$ and every $y\in A_{n+1}$, the edge $\{x_m,y\}$ is red.

Start with $A_0:=\omega$ and $x_0:=\min(A_0)=0$. Suppose $A_n$ and $x_n$ are defined and $A_n$ is infinite. Partition $A_n\setminus\{x_n\}$ into \[ B_n:=\{y\in A_n: y\neq x_n,\ c(\{x_n,y\})=\text{blue}\},\qquad R_n:=\{y\in A_n: y\neq x_n,\ c(\{x_n,y\})=\text{red}\}. \] If $B_n$ is infinite, then by Lemma lem:blue_nhood_red the set $B_n$ is a red clique. Also, by the inductive property $3$ with $A_n$ in place of $A_{n+1}$, every earlier $x_m$ ($m<n$) is red-adjacent to every vertex of $A_n$, hence to every vertex of $B_n$. Therefore $\{x_0,\dots,x_{n-1}\}\cup B_n$ is an infinite red clique. In particular, we can extract from it an increasing red clique of order type $\omega$, and we are done.

If instead $B_n$ is finite, then $R_n$ is infinite (since $A_n\setminus\{x_n\}$ is infinite). Define $A_{n+1}:=R_n$ and $x_{n+1}:=\min(A_{n+1})$. Condition $1$ and $2$ hold by construction. Condition $3$ holds because for $m<n$, every $x_m$ was red-adjacent to every element of $A_n$ by the inductive hypothesis, and by definition every element of $A_{n+1}=R_n\subseteq A_n$ is red-adjacent to $x_n$.

Thus either the process terminates at some stage (giving an infinite red clique immediately), or it continues for all $n<\omega$. In the latter case, for any $i<j$, we have $x_j\in A_i$ by repeated application of $2$, hence $c(\{x_i,x_j\})=\text{red}$ by $3$. Therefore $(x_n)_{n<\omega}$ is an infinite increasing red clique as required.$\square$

Lemma 3 (restriction gives a red $\omega^\omega$ inside $\omega^{\omega^2}$ under "no blue triangle"). Assume the theorem stated in the problem text for $\omega^\omega$: every red/blue colouring of $[\omega^\omega]^2$ contains either a red $K_{\omega^\omega}$ or a blue $K_3$. Then for $\alpha=\omega^{\omega^2}$, any colouring $c:[\alpha]^2\to\{\text{red},\text{blue}\}$ with no blue triangle contains a red $K_{\omega^\omega}$.

Proof. Since $\omega^\omega<\omega^{\omega^2}$, the initial segment $S:=\{\xi<\alpha: \xi<\omega^\omega\}$ has order type $\omega^\omega$. Restrict $c$ to $[S]^2$. This restricted colouring has no blue triangle (any blue triangle inside $S$ would also be a blue triangle in $\alpha$). By the assumed theorem for $\omega^\omega$, the restriction must therefore contain a red $K_{\omega^\omega}$. That is, there exists $T\subseteq S$ of order-type $\omega^\omega$ such that all edges in $[T]^2$ are red. Since $T\subseteq\alpha$, this is also a red $K_{\omega^\omega}$ in $K_\alpha$.$\square$

VERIFICATION

• Lemma lem:blue_nhood_red: checked that the only needed hypothesis is "no blue triangle"; no ordinal-specific assumption is used.
• Lemma lem:omega_case: the recursion maintains that $A_n$ is infinite unless we already have an infinite red clique from an infinite $B_n$. The conclusion produces an increasing red clique, hence order type $\omega$.
• Lemma lem:restrict_omegaomega: the only nontrivial input is the $\omega^\omega$ statement, which is explicitly mentioned in the problem text (attributed to Chang). The rest is a restriction argument.

FINAL

UNRESOLVED

(i) Strongest proved partial result. If a colouring $c:[\omega^{\omega^2}]^2\to\{\text{red},\text{blue}\}$ has no blue triangle, then (by restricting to an initial segment of type $\omega^\omega$ and using the $\omega^\omega$ result stated in the problem text) it contains a red $K_{\omega^\omega}$ (Lemma lem:restrict_omegaomega). In particular, any counterexample to $\omega^{\omega^2}\to(\omega^{\omega^2},3)^2$ must still contain very large red cliques (of type $\omega^\omega$).

(ii) First gap (crisp). Given a blue-triangle-free colouring $c:[\omega^{\omega^2}]^2\to\{\text{red},\text{blue}\}$, prove or refute that there exists $X\subseteq\omega^{\omega^2}$ of order type $\omega^{\omega^2}$ with all edges in $[X]^2$ red.

(iii) Top 3 next moves.

1. Prove an "upgrade lemma": assuming no blue triangle, show that from cofinally many red copies of $\omega^{\omega\cdot m}$ one can build a red copy of $\omega^{\omega\cdot(m+1)}$.
2. Develop a canonical form for triangle-free-blue colourings on $\omega^{\omega^2}$ (e.g. by analyzing colors between blocks in the natural decomposition $\omega^{\omega^2}=\sup_{m<\omega}\omega^{\omega\cdot m}$).
3. Search for an explicit Specker-type triangle-free-blue colouring on $\omega^{\omega^2}$ that destroys red copies of order type $\omega^{\omega^2}$; even a concrete candidate on the subordinal $\omega^{\omega\cdot 2}$ would be informative.

(iv) Minimal counterexample structure. A minimal counterexample would be a colouring on $\omega^{\omega^2}$ with no blue triangle and no red $K_{\omega^{\omega^2}}$; by Lemma lem:restrict_omegaomega it would still contain a red $K_{\omega^\omega}$. Thus any counterexample must allow very large red cliques while preventing their extension to order type $\omega^{\omega^2}$, likely by forcing many blue edges between different "$\omega^\omega$-blocks" without ever creating a blue triangle.