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.


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.

Read the rest of this entry »


187 – On Ramsey theory

May 4, 2010

Given a natural number {n}, write {K_n} for the complete graph on {n} vertices, and {E_n} for the edgeless graph on {n} vertices.

As explained in problem 47.10 from the textbook, given natural numbers {a,b,n}, the notation

\displaystyle  n\rightarrow(a,b)

means that {n} is so large that whenever {G} is a graph on {n} vertices, either {G} contains a copy of {K_a} as a subgraph, or a copy of {E_b} as an induced subgraph.

We denote the negation of this statement by {n\not\rightarrow(a,b)}. In detail, this means that there is a graph {G=(V,E)} on {n} vertices such that for any collection of {a} vertices of {G}, at least one of the edges between them is not in {E}, and also for any collection of {b} vertices of {G}, at least of the edges between them is in {E}.

Note that if {n\rightarrow(a,b)} then also:

  • {n\rightarrow(b,a)},
  • {m\rightarrow(a,b)} for any {m\ge n}, and
  • {n\rightarrow(a,c)} for any {c\le b}.

Clearly, {0\rightarrow(m,0)} and {1\rightarrow(m,1)} for any {m}. It is also clear that {m\rightarrow(m,2)} for any {m}. When {a,b\ge3}, however, the determination of the smallest {n} such that {n\rightarrow(a,b)} is a subtle and difficult problem. This {n} is called the Ramsey number of {a,b}. We will denote it {R(a,b)}, so

\displaystyle  R(a,b)\rightarrow(a,b)

and, if {m<R(a,b)}, then {m\not\rightarrow(a,b)}. Read the rest of this entry »