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.

Read the rest of this entry »


Summer Kisner – Schur’s theorem

May 19, 2013

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

2013--5-18 Summer

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 \mathbb Z^+ are partitioned into finitely many sets, \mathbb Z^+=A_1\cup\dots\cup A_n, then for some i, 1\le i\le n, there are integers x,y,z (not necessarily different), all of them in A_i, such that x+y=z. One usually describes this in terms of colors: We color the positive integers with finitely many colors, and there is a monochromatic triple x,y,z with x+y=z.

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 {}[X]^k denote the collection of k-sized subsets of the set X. Suppose that X is infinite, and consider a coloring c:[X]^k\to C, where the set C of colors is finite. Ramsey’s theorem asserts that under these assumptions, there is an infinite subset H of X that is homogeneous or monochromatic for c, in the sense that c assigns the same color to all k-sized subsets of H. In fact, we have finitary versions of this result: For any n and any l=|C|, if we only require that H has size at least n, then there is an m such that it suffices to assume that X has size at least m. Even for k=l=2, the study of Ramsey numbers, the least m seen as a function of n, proves to be incredibly difficult and computationally unfeasible. For example, if n=5, then we know that 43\le m\le 49, but its exact value is not known.

To deduce Schur’s theorem from Ramsey’s, let r be such that, for any for coloring of {}[\{1,\dots,r\}]^2 using n colors, there is a monochromatic set of size 3. The least such r we denote R_n(3). We want to show that if \mathbb Z^+=A_1\cup\dots\cup A_n, then there is a monochromatic solution to the equation x+y=z. In fact, we claim that it suffices to consider \{1,\dots,r-1\} rather than the whole set of positive integers. Indeed, given a partition \{1,\dots,r-1\}=A_1\cup\dots\cup A_n, consider the coloring of {}[\{1,\dots,r\}]^2 where if a<b, then the set $\{a,b\}$ has color i, where b-a\in A_i. By definition of r, we can find a<b<c such that \{a,b\},\{a,c\},\{b,c\} all have the same color. Now notice that c-a=(c-b)+(b-a), that is, b-a,c-b,c-a are monochromatic for the original coloring of \{1,\dots,r-1\}.

An easy inductive argument gives us that R_n(3)\le 3\cdot n!, so this gives the upper bound 3\cdot n!-1 for the so-called n-th Schur number s(n). To see the upper bound R_n(3)\le 3\cdot r!, note that R_1(3)=3, and verify inductively that R_{n+1}(3)\le (n+1)R_n(3): Suppose that |X|\ge (n+1)R_n(3), and consider a coloring of [X]^2 with n+1. Fix an element a\in X, and note that for some color i there are R_n(3) elements b\in X such that \{a,b\} has color i. Let Y be the set of all these b, that is, Y=\{b\in X\mid\{a,b\} has color i\}. Note that if for some b,c\in Y we have that \{b,c\} has color i as well, then \{a,b,c\} is monochromatic with color i. Hence we may assume that the coloring, restricted to {}[Y]^2, only uses n colors. We are now done, since |Y|\ge R_n(3).

Schur’s original proof predated Ramsey, and gives a slightly better bound than s(n)\le 3\cdot n!. Indeed, from his proof, we obtain that s(n)\le \lceil n!e\rceil.

In terms of lower bounds, one can quickly check by induction that s(n)\ge (3^n+1)/2. Indeed, s(1)=2=(3^1+1)/2, since 1+1=2. Given a coloring c of \{1,\dots,k\} using colors \{1,\dots,n\} and without monochromatic triples, we describe a coloring c' of \{1,\dots,3k+1\} using colors \{1,\dots,n+1\}, again without monochromatic triples. This gives the result. To define c', start by letting c'(i)=c(i) for i\le k. Now let c'(j)=n+1 for k+1\le j\le 2k+1, and finally let c'(j)=c(j-(2k+1)) for 2k+2\le j\le 3k+1.

Slightly better bounds are known. For example, Anne Penfold Street shows that s(n)\ge (89\cdot 3^{n-4}+1)/2 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 x, y, z are integers, and x^n+y^n=z^n. Then, for any prime p, the equality holds modulo p and, if p is large enough, then we also have that p\not\mid xyz. Hence, to prove that Fermat’s equation admits no solutions (x,y,z), it would suffice to show that there are arbitrarily large primes p such that p must divide one of x,y,z. What Schur proved is that this is not possible and, indeed, for any n and all sufficiently large primes p, there are nontrivial solutions to Fermat’s equation modulo p. To see this, let p>s(n) and let G be the subgroup of (\mathbb Z/p\mathbb Z)^* consisting of n-th powers. Then (\mathbb Z/p\mathbb Z)^* is union of cosets of G, say (\mathbb Z/p\mathbb Z)^*=\bigcup_{i=1}^k a_iG where the k displayed sets are disjoint. Note that k=n/\mathrm{gcd}(n,p-1)\le n. Now color (\mathbb Z/p\mathbb Z)^* using k colors, by letting t have color i iff t\in a_iG. By choice of p, we have a monochromatic Schur triple, that is, there are \alpha,\beta,\gamma\in (\mathbb Z/p\mathbb Z)^* such that \alpha+\beta=\gamma and \alpha,\beta,\gamma\in a_iG for some i. But then there are x,y,z, all nonzero modulo p, such that \alpha=a_i x^n, \beta=a_i y^n, and \gamma=a_i z^n, so (x,y,z) is a nontrivial solution to Fermat’s equation modulo p.

It is actually an interesting problem to try and determine the optimal size \mathcal N of p as a function of n. Fourier-analytic methods give here the best known bounds. Cornacchia proved in 1909 that \mathcal N(n)\le (n-1)^2(n-2)^2+6n-2, at least if n 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 n there is an s'(n) such that if \{1,2,\dots,s'(n)\} is colored using n colors, then there is a monochromatic set \{x,y,z\} with xy=z. Indeed, this follows as a simple corollary of Schur’s result: Just note that s'(n)\le 2^{s(n)}, 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 \mathbb Z^+ there are integers x,y such that x,y,x+y,xy all receive the same color. This was originally asked by Hindman.


580 -III. Partition calculus

March 21, 2009

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 {\mbox{Erd\H os}}-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 {\mbox{Erd\H os},} 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-{\mbox{\bf \v Cech}} compactification, De Gruyter, (1998).
  • Stevo {\mbox{Todor\v cevi\'c},} High-dimensional Ramsey theory and Banach space geometry, in Ramsey methods in Analysis, Spiros Argyros, Stevo {\mbox{Todor\v cevi\'c},} 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.

Read the rest of this entry »