Erdős Problem #590

Erdős Problem #590: the ordinal $\omega^\omega$

Restricted coloring theorem with the order type preserved, 24 September 2026.

Exact statement

Does $\omega^\omega\to(\omega^\omega,3)^2$ hold? The large red clique must have order type $\omega^\omega$ in the given order, not merely countably many vertices. Chang proved the affirmative answer, later strengthened and shortened by Milner and Larson. We prove the full conclusion when the blue graph has finite chromatic number, and explain precisely why this leaves the general triangle-free case open in this attempt.

Finite partitions of the underlying ordinal

First, every finite partition of $\omega^n$, for a positive integer $n$, has a class of order type $\omega^n$. For $n=1$, this is the infinite pigeonhole principle. For the induction step, decompose $\omega^{n+1}$ into consecutive blocks of type $\omega^n$. In each block the induction hypothesis gives a full-type subset in one class. The same class occurs for infinitely many block indices; its union in those blocks has type $\omega^n\cdot\omega=\omega^{n+1}$.

Next write $\omega^\omega$ as the ordinal sum of consecutive blocks of types $\omega,\omega^2,\omega^3,\ldots$. Given finitely many classes, each block contains a full-type subset in one class. One class is selected for infinitely many, hence unbounded, block indices $n_j$. Their union has type \[\sum_{j<\omega}\omega^{n_j}=\omega^\omega. \] For completeness, its order type is at most the ambient ordinal, while for every finite $m$ it contains a subset of type $\omega^m$ in a selected block. Its type is consequently at least $\sup_m\omega^m=\omega^\omega$. This proves the finite-partition assertion.

Applying the lemma to an edge coloring

Form the graph whose edges are exactly the blue pairs. If this graph admits a proper coloring with $q<\omega$ colors, each vertex color class is a red clique. The partition assertion supplies a class of order type $\omega^\omega$, giving the desired red clique. In particular this proves the statement whenever blue degrees are bounded by a finite integer $d$: enumerate the countable vertex set and greedily assign one of $d+1$ colors, avoiding the colors of earlier blue neighbors.

There is another useful sufficient condition. If a vertex has a blue neighborhood of order type $\omega^\omega$ and there is no blue triangle, that entire neighborhood is red-complete: a blue pair inside it would complete a blue triangle through the vertex. Thus an unsuccessful coloring in the present approach must have infinite blue chromatic number and every blue neighborhood of smaller order type.

Why ordinary infinite Ramsey theory does not finish this

A coloring with no blue triangle always has an infinite red clique. One direct proof repeatedly selects a vertex from an infinite remaining set. If it has infinitely many blue neighbors there, those neighbors form a red clique. Otherwise discard its finitely many blue neighbors and retain its infinite red neighborhood for the next step. If this never terminates, the selected vertices form an infinite red clique. However, an infinite subset of $\omega^\omega$ can have type only $\omega$, for example one point from each of the blocks above. The recursion therefore does not prove the required order type. Nor does triangle-freeness imply finite chromatic number, so it does not justify the finite-partition application without its additional hypothesis.

Outcome and remaining gap

Attempt status: unresolved. The finite-blue-chromatic case, its bounded-degree corollary and the neighborhood obstruction are completely proved. The missing step is the ordinal structure needed for arbitrary triangle-free blue graphs of infinite chromatic number. Chang's general theorem is a known result, not a theorem reproved here. Sources: https://www.erdosproblems.com/590; C. C. Chang, A partition theorem for the complete graph on $\omega^\omega$, J. Combinatorial Theory A 12 $1972$, 396--452; J. A. Larson, A short proof of a partition theorem for the ordinal $\omega^\omega$, Ann. Math. Logic 6 $1973/74$, 129--145. Bibliography: https://www.erdosproblems.com/latex/590. No novelty or local formal verification is claimed.

COMPLETION ESTIMATE

COMPLETION: 30%