Ramsey’s theorem is probably the most famous result of Ramsey theory, giving it its name. Essentially it states that a finite coloring of a certain structure contains a monochromatic copy of the original structure, in this case the structure being a complete (hyper)graph.
Another theorem which became very important in recent decades is Hindman’s finite sums theorem. This theorem also says that a finite coloring of a certain structure contains a monochromatic copy of the original structure, in this case the structure is that of an IP-set.
As it happens often in mathematics (and more so, apparently, in Ramsey theory) there exists a unifying theorem which contains both Ramsey’s and Hindman’s as special cases. This is the Milliken-Taylor theorem (discovered independently by Keith Milliken and Alan D. Taylor while they were graduate students).
In this post I will present these three theorems and discuss how they are related.
— 1. Ramsey’s theorem —
There are several formulations of Ramsey’s theorem. The one below is that which most people are familiar with:
Theorem 1 (Ramsey theorem) For every there exists some such that if the edges of the complete graph with vertices are colored in colors, than one can find vertices such that the complete graph formed by them has all edges of the same color.
This can be extended to hypergraphs. If we denote by the set . Also if is a set and we denote by the family of all subsets of of cardinality .
Both Theorems 1 and 2 are called finitistic versions, because every object in these statements is finite. They have corresponding infinite versions. Since Theorem 2 implies Theorem 1, I will just state the infinite version of the former.
One can deduce Theorem 2 from Theorem 3 easily, using a compactness argument. However, the other direction is not true is a very precise sense. Indeed the infinite Ramsey theorem implies a strengthening of Theorem 2 which can not be proved under the Peano axioms (while theorem 2 itself can be proved under the Peano axioms); this is the content of the Paris-Harrington theorem.
Observe that in each of the theorems above, the only property about the sets and we care about is their cardinality; the only reason to stick to those concrete sets is to make the proofs easier to read. We now recall the proof of Theorem 3 for :
Proof: Fix and a finite coloring . Applying the pigeonhole principle, there exists an infinite set such that the family
is monochromatic (such exists by the pigeonhole principle).
For each let be the color of the family (1). Applying the pigeonhole again we can find an infinite increasing sequence and a color such that for all . Thus for any pair we have that
and hence . This means that taking we have that is monochromatic.
We can now bootstrap this argument to prove the general case of Theorem 3 (with any ).
We proceed by induction on , the case having been proved above (and the case being the pigeonhole principle). Now assume that and, for each , let be the coloring defined by for any .
Applying the induction hypothesis, there exists an infinite set such that is monochromatic with respect to . This means that the family
is monochromatic with respect to .
is monochromatic for .
Let be the color of the family (2). Applying the pigeonhole again we can find an infinite increasing sequence and a color such that for all . Let ; we claim that is monochromatic (with color ).
Indeed, let and let . Then each of the elements of different than are of the form for some . This means that . We conclude that .
Analyzing the proof we see that Theorem 3 with is just a (cleverly arranged) iteration of the almost trivial pigeonhole principle, while the general case is just an iteration (or induction) of the case .
Thus it seems natural to try to run the same process fueled by a stronger version of the pigeonhole principle. What is meant by a stronger version of the pigeonhole principle (or which versions can fuel this type of argument) is not clear, but it turns out that Hindman’s theorem is suitable for this program.
— 2. Hindman’s theorem —
The formulation of Hindman’s theorem is very simple, at least when one knows what an IP-set is:
Theorem 4 For any finite coloring of an IP-set there exists a monochromatic sub IP-set.
An IP-set is an infinite set together with all the sums of finite subsets of . I have mentioned IP-sets before in this blog and I gave a proof of Hindman’s theorem (as stated here it follows from this and this).
Note that is itself an IP-set, generated by , because every natural number is the sum of some distinct powers of . Because this representation is unique, Theorem 4 is equivalent to the fact that any finite coloring of contains a monochromatic IP-set.
When talking about IP-sets it is usually convenient to introduce the symbol to the denote the family of all finite non-empty subsets of . Thus if is an increasing sequence and for each , the IP-set generated by is the set .
It is trivial that for any disjoint and indeed if is any “sequence” indexed by such that for any disjoint , then the set is an IP-set (generated by ). For this reason we can refer to a generic IP-sets as , generated by the sequence where . We will always assume that a sequence generating an IP-set is increasing. The notion of a sub-IP has more than one (non-equivalent) natural concrete definition. It seems that most theorems remain true regardless of which variant one chooses, so for our purposes we will use the following strong definition:
Definition 5 Let be IP-sets.
- For we write as a shortcut to .
- We say that is a sub-IP of if there exist such that for all .
Equivalently, a sub-IP of an IP-set generated by an infinite set (so that contains and all the sums of finite subsets of ) is the IP-set generated by a set of the form
and are finite subsets of (and so contains together with all the sums of finite subsets of ).
It will be convenient to consider a particular type of sub-IPs.
Definition 6 (Shifted IP-sets) Let be an IP-set generated by and let . Then we denote by the sub-IP of generated by the sequence .
Thus a shifted IP-set is just the tail of the original IP-set, after losing the first generators.
— 3. Milliken-Taylor —
Definition 7 Let be an IP-set and let . We define to be the family of the -tuples such that .
Theorem 8 (Milliken-Taylor) For any , any IP-set and any finite coloring of , there exists a sub-IP of such that is monochromatic.
As I hinted at above the proof of this result follows very closely the proof of Ramsey’s theorem with each application of the pigeonhole principle replaced with an application of Hindman’s theorem. In the proof below I try to make clear what is similar and what is not.
Because the objects we use are a little technical I spend some time making the steps clear, which makes the proof look longer than it actually is.
Proof: Let and let be arbitrary. Passing, if necessary to a sub-IP we can (and will) assume that for .
We proceed by induction on , the case being Hindman’s theorem. Now assume that and that the result has been established for .
is monochromatic with respect to .
Before we summarize the full induction it is instructive go to through the second step, because the main novelty of this proof (when compared to the proof of Ramsey’s theorem) appears now.
Let be defined by
Applying the induction hypothesis, there exists a sub-IP of such that is monochromatic with respect to . This means that both families
are monochromatic with respect to , although possibly of different colors.
Now let , and . In the next lemma we summarize the induction step:
Proof: Assume the IP-sets have been found for all . Define the coloring by letting
Applying the induction hypothesis we can now extract a sub-IP of such that is monochromatic with respect to . However, that means that (4) is monochromatic whenever contains .
Let as in the lemma. Observe that, for each , Lemma 9 implies that the family
is monochromatic, where . Define the coloring by assigning to the color of the family (5). By Hindman theorem there exists a sub-IP of monochromatic under . By construction we have that the color of the family
does not depend on . This is equivalent to say that is monochromatic as desired.
An interesting corollary of this result arises by making the color of a set depend only on the sum , or more generally on some fixed linear combination of the elements of .
Definition 10 Let , let and let be an IP-set. We define
Proof: Let be given by
Applying Milliken-Taylor’s Theorem 8 we find a sub-IP of such that is monochromatic with respect to . This implies that is monochromatic with respect to as desired.
In fact, Theorem 8 also follows from Corollary 11 (for the proof we first need to pass to a sparse enough sub-IP so that for all . This implies that there is a bijection between and ), and so both versions are equivalent.