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 \betath 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).

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: