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 , 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 for finite.

Given nonzero ordinals , recall that is the least such that any red-blue coloring of the edges of either admits a red copy of or a blue copy of . Clearly , if , and , so we may as well assume that , 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 is finite whenever are finite, and his second result states that . The computation of the numbers is an extremely difficult, most likely unfeasible, problem, though 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 is already . Hence, if we are interested in studying the countable values of the function , then we must assume that either , in which case and there is nothing more to say, or else (that is, if is countable and strictly larger than ) we must assume that is finite.

The function has been intensively studied when is a limit ordinal, particularly a power of . Here we look at the much humbler setting where . 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 there exists a positive integer such that for any red-blue coloring of the edges of , and such that is blue, there is a subset of with monochromatic, and either is blue and , or else is red, , and .

Denote by the smallest number witnessing the lemma.

Theorem. If are positive integers, then , where .

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.

Advertisement

Summer Kisner – Schur’s theorem

My student Summer Kisner completed her M.S. this term, and graduated on Saturday.

2013–5-18 Summer

Here is a copy of the slides she used on her defense. (The slides display incorrectly on my computer, but it seems to be a problem on my end. If it is not, please let me know, and I’ll see what I can do.)

Her thesis, Schur’s theorem and related topics in Ramsey theory, discusses Schur’s theorem, one of the first result in what we now call Ramsey theory. The result states that if the positive integers are partitioned into finitely many sets, , then for some , , there are integers (not necessarily different), all of them in , such that . One usually describes this in terms of colors: We color the positive integers with finitely many colors, and there is a monochromatic triple with .

This result is a cornerstone of Ramsey theory. It was significantly generalized by Rado (using the notion of partition regularity), and is connected to van der Waerden’s and Szemerédi’s famous results.

Nowadays, Schur’s theorem is typically proved as a corollary of Ramsey’s theorem. This is usually stated in terms of graphs, but I will use the notation from the partition calculus. Let denote the collection of -sized subsets of the set . Suppose that is infinite, and consider a coloring , where the set of colors is finite. Ramsey’s theorem asserts that under these assumptions, there is an infinite subset of that is homogeneous or monochromatic for , in the sense that assigns the same color to all -sized subsets of . In fact, we have finitary versions of this result: For any and any , if we only require that has size at least , then there is an such that it suffices to assume that has size at least . Even for , the study of Ramsey numbers, the least seen as a function of , proves to be incredibly difficult and computationally unfeasible. For example, if , then we know that , but its exact value is not known.

To deduce Schur’s theorem from Ramsey’s, let be such that, for any for coloring of using colors, there is a monochromatic set of size . The least such we denote . We want to show that if , then there is a monochromatic solution to the equation . In fact, we claim that it suffices to consider rather than the whole set of positive integers. Indeed, given a partition , consider the coloring of where if , then the set $\{a,b\}$ has color , where . By definition of , we can find such that all have the same color. Now notice that , that is, are monochromatic for the original coloring of .

An easy inductive argument gives us that , so this gives the upper bound for the so-called -th Schur number . To see the upper bound , note that , and verify inductively that : Suppose that , and consider a coloring of with . Fix an element , and note that for some color there are elements such that has color . Let be the set of all these , that is, has color . Note that if for some we have that has color as well, then is monochromatic with color . Hence we may assume that the coloring, restricted to , only uses colors. We are now done, since .

Schur’s original proof predated Ramsey, and gives a slightly better bound than . Indeed, from his proof, we obtain that .

In terms of lower bounds, one can quickly check by induction that . Indeed, , since . Given a coloring of using colors and without monochromatic triples, we describe a coloring of using colors , again without monochromatic triples. This gives the result. To define , start by letting for . Now let for , and finally let for .

Slightly better bounds are known. For example, Anne Penfold Street shows that in

 W.D. Wallis, Anne Penfold Street, Jennifer Seberry Wallis. Combinatorics: Room squares, sum-free sets, Hadamard matrices. Lecture Notes in Mathematics, Vol. 292. Springer-Verlag, Berlin-New York, (1972). MR0392580 (52 #13397).

Schur proved his theorem in order to establish a result related to Fermat’s last theorem, namely that it cannot be established by a naive argument involving modular arithmetic: Suppose that are integers, and . Then, for any prime , the equality holds modulo and, if is large enough, then we also have that . Hence, to prove that Fermat’s equation admits no solutions , it would suffice to show that there are arbitrarily large primes such that must divide one of . What Schur proved is that this is not possible and, indeed, for any and all sufficiently large primes , there are nontrivial solutions to Fermat’s equation modulo . To see this, let and let be the subgroup of consisting of -th powers. Then is union of cosets of , say where the displayed sets are disjoint. Note that . Now color using colors, by letting have color iff . By choice of , we have a monochromatic Schur triple, that is, there are such that and for some . But then there are , all nonzero modulo , such that , , and , so is a nontrivial solution to Fermat’s equation modulo .

It is actually an interesting problem to try and determine the optimal size of as a function of . Fourier-analytic methods give here the best known bounds. Cornacchia proved in 1909 that , at least if itself is prime.

Let me close with an open problem: We could consider a multiplicative (rather than additive) version of Schur’s theorem: For any there is an such that if is colored using colors, then there is a monochromatic set with . Indeed, this follows as a simple corollary of Schur’s result: Just note that , since we could just color the powers of two and apply the additive version. what if we combine the two? It is still open whether in any finite coloring of there are integers such that all receive the same color. This was originally asked by Hindman.

580 -III. Partition calculus

1. Introduction

Partition calculus is the area of set theory that deals with Ramsey theory; it is devoted to Ramsey’s theorem and its infinite and infinitary generalizations. This means both strengthenings of Ramsey’s theorem for sets of natural numbers (like the Carlson-Simpson or the Galvin-Prikry theorems characterizing the completely Ramsey sets in terms of the Baire property) and for larger cardinalities (like the -Rado theorem), as well as variations in which the homogeneous sets are required to possess additional structure (like the Baumgartner-Hajnal theorem).

Ramsey theory is a vast area and by necessity we won’t be able to cover (even summarily) all of it. There are many excellent references, depending on your particular interests. Here are but a few:

• Paul András Hajnal, Attila Máté, Richard Rado, Combinatorial set theory: partition relations for cardinals, North-Holland, (1984).
• Ronald Graham, Bruce Rothschild, Joel Spencer, Ramsey theory, John Wiley & Sons, second edn., (1990).
• Neil Hindman, Dona Strauss, Algebra in the Stone- compactification, De Gruyter, (1998).
• Stevo High-dimensional Ramsey theory and Banach space geometry, in Ramsey methods in Analysis, Spiros Argyros, Stevo Birkhäuser (2005), 121–257.
• András Hajnal, Jean Larson, Partition relations, in Handbook of set theory, Matthew Foreman, Akihiro Kanamori, eds., to appear.

I taught a course on Ramsey theory at Caltech a couple of years ago, and expect to post notes from it at some point. Here we will concentrate on infinitary combinatorics, but I will briefly mention a few finitary results.