## Ramsey theory of very small countable ordinals

November 6, 2014

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.