## Ramsey theory of very small countable ordinals

I was an undergraduate student at Los Andes, from 1992 to 1996. This year, their mathematics program is turning 50. There was a conference in September to celebrate the event, and I had the honor to give one of the talks (see here for the English version of the slides).

The Faculty of Science publishes a magazine, Hipótesis, and a special edition will be devoted to the conference. I have submitted an expository paper, based on my talk.

The topic is the partition calculus of very small countable ordinals (mainly ordinals below $\omega^2$, actually). The paper reviews Ramsey’s theorem and a few finite examples, before discussing the two main results.

1.

One is an old theorem by Haddad and Sabbagh, unfortunately not well known. In 1969, they computed the Ramsey numbers $r(\omega+n,m)$ for $n,m$ finite.

Given nonzero ordinals $\alpha,\beta$, recall that $r(\alpha,\beta)$ is the least $\gamma$ such that any red-blue coloring of the edges of $K_\gamma$ either admits a red copy of $K_{\alpha}$ or a blue copy of $K_\beta$. Clearly $r(\alpha,1)=1$, $r(\alpha,\beta)\ge r(\alpha,2)=\alpha$ if $\beta\ge2$, and $r(\alpha,\beta)=r(\beta,\alpha)$, so we may as well assume that $\alpha\ge\beta>2$, and we adopt this convention in what follows.

Ramsey proved two theorems about this function in a famous 1928 paper that introduced the topic. In the notation we have just set up, his first result asserts that $r(n,m)$ is finite whenever $n,m$ are finite, and his second result states that $r(\omega,\omega)=\omega$. The computation of the numbers $r(n,m)$ is an extremely difficult, most likely unfeasible, problem, though $r$ is obviously a recursive function. We are concerned here with the values of the function when at least one of the arguments is infinite.

It turns out that $r(\omega+1,\omega)$ is already $\omega_1$. Hence, if we are interested in studying the countable values of the function $r(\alpha,\beta)$, then we must assume that either $\omega=\alpha$, in which case $r(\alpha,\beta)=\omega$ and there is nothing more to say, or else (that is, if $\alpha$ is countable and strictly larger than $\omega$) we must assume that $\beta$ is finite.

The function has been intensively studied when $\alpha$ is a limit ordinal, particularly a power of $\omega$. Here we look at the much humbler setting where $\omega<\alpha<\omega2$. Recalling that each ordinal equals the set of its predecessors, and using interval notation to describe sets of ordinals, the Haddad-Sabbagh result is as follows:

Lemma. For all positive integers $n, m$ there exists a positive integer $k\ge n, m$ such that for any red-blue coloring of the edges of $K_{[0,k)}$, and such that $K_{[0,m)}$ is blue, there is a subset $H$ of ${}[0, k)$ with $K_H$ monochromatic, and either $K_H$ is blue and $|H| = m + 1$, or else $K_H$ is red, $|H|=n+1$, and $H\cap[0,m)\ne\emptyset$.

Denote by $r_{HS}(n+1,m+1)$ the smallest number $k$ witnessing the lemma.

Theorem. If $n,m$ are positive integers, then $r(\omega +n,m)=\omega(m-1)+t$, where $r_{HS}(n+1,m)=(m-1)+t$.

The theorem was announced in 1969, but the proof never appeared. I have written a survey on the topic, including what should be the first proof in print of this result.

2.

A topological variant of the function $r$ is obtained by requiring that the homogeneous set be a faithful topological copy of the corresponding ordinal. The resulting function we denote $r_{cl}$. Formally, $r_{cl}(\alpha,\beta)=\gamma$ iff $\gamma$ is least such that any for red-blue coloring of $K_\gamma$ there is an $H\subseteq\gamma$ such that $K_H$ is monochromatic and, if $K_H$ is red, then $H$ is  order-homeomorphic to $\alpha$, or if $K_H$ is blue, then $H$ is order-homeomorphic to $\beta$.

The notion of order-homeomorphism is a natural one, the name itself is due to Baumgartner. We say that a set of ordinals $H$ is order-homeomorphic to an ordinal $\alpha$ iff, first of all, $H$ has order type $\alpha$ and, second, the unique order-isomorphism between $H$ and $\alpha$ is a homeomorphism. Here, ordinals are equipped with the order topology, and $H$ carries the subspace topology (it is easy to check that if $H\subseteq\beta\le\gamma$, then the topology inherited by $H$ as a subspace of $\beta$ is the same as the topology inherited as a subspace of $\gamma$. More concretely, the topological component of the definition simply assert that, for any limit ordinal $\beta<\alpha$, the $\beta$th element of $H$ is the supremum of its predecessors in $H$. That is, $H$ is closed as a subset of its supremum.

To illustrate the difference between $r$ and $r_{cl}$, let me mention that $r(\omega+1,3)=\omega2+1$ but $r_{cl}(\omega+1,3)=\omega^2+1$, and $r(\omega+2,3)=\omega2+4$ but $r_{cl}(\omega+2,3)=\omega^22+\omega+2$.

Theorem. The ordinal $r_{cl}(\omega n+m,k)$ is countable for all finite $n,m,k$.

The proof provides concrete upper bounds. The argument proceeds by induction, the key technical tool being the function $r_{cl}(\alpha,\beta;1)$ that allows us to study the closed version of the pigeonhole principle:

One can prove that for all $\alpha,\beta$ there is a $\gamma$ such that whenever $\gamma=A\cup B$, either $A$ contains a subset order-homeomorphic to $\alpha$, or else $B$ contains a subset order-homeomorphic to $\beta$. The smallest possible $\gamma$ with this property we denote $r_{cl}(\alpha,\beta;1)$.

For example, $r_{cl}(\omega+1,\omega+1;1)=\omega^2+1$, and $r_{cl}(\omega+2,\omega+2;1)=\omega^2+\omega+2$. To verify that $r_{cl}(\omega+2,3)=\omega^22+\omega+2$, what one actually proves is that $r_{cl}(\omega+2,3)=r_{cl}(\omega+1,3)+r_{cl}(\omega+2,\omega+2;1)$.