Ramsey, Hindman and Milliken-Taylor Theorems

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 {r,k\in{\mathbb N}} there exists some {N\in{\mathbb N}} such that if the edges of the complete graph with {N} vertices are colored in {r} colors, than one can find {k} vertices such that the complete graph formed by them has all edges of the same color.

This can be extended to hypergraphs. If {N\in{\mathbb N}} we denote by {[N]} the set {\{1,2,\dots,N\}}. Also if {S} is a set and {m\in{\mathbb N}} we denote by {\binom Sm} the family of all subsets of {S} of cardinality {m}.

Theorem 2 (Hypergraph Ramsey theorem) For every {r,k,m\in{\mathbb N}} there exists some {N\in{\mathbb N}} such that if we color {\binom{[N]}m} with {r} colors we can find a subset {S\subset[N]} with cardinality {|S|=k} such that the family {\binom Sm\subset\binom{[N]}m} is monochromatic.

It should be clear that Theorem 2 with {m=2} is equivalent to Theorem 1, since the edges of a complete graph are simply all the subsets with two elements of the set of vertices.

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.

Theorem 3 (Infinite Hypergraph Ramsey Theorem) For any {m\in{\mathbb N}} and any coloring of {\binom{\mathbb N} m} into finitely many colors, there exists an infinite set {S\subset{\mathbb N}} such that the family {\binom Sm\subset\binom{\mathbb N} m} is monochromatic.

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 {[N]} and {{\mathbb N}} 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 {m=2}:

Proof: Fix {r\in{\mathbb N}} and a finite coloring {\chi:\binom{\mathbb N}2\rightarrow[r]}. Applying the pigeonhole principle, there exists an infinite set {S_1\subset{\mathbb N}\setminus\{1\}} such that the family

\displaystyle \big\{\{1,x\}:x\in S_1\big\}

is monochromatic. Now we let {x_0=1} and create inductively an increasing sequence {(x_n)_{n\in{\mathbb N}}} of positive integers and a sequence {(S_n)_{n\in{\mathbb N}}} of infinite subsets of {{\mathbb N}} by letting, for each {n\geq1}, {x_n=\min S_n} and {S_{n+1}\subset S_n\setminus\{x_n\}} be such that the family

\displaystyle \big\{\{x_n,x\}:x\in S_{n+1}\big\} \ \ \ \ \ (1)

is monochromatic (such {S_{n+1}} exists by the pigeonhole principle).

For each {n\geq0} let {t_n\in[r]} be the color of the family (1). Applying the pigeonhole again we can find an infinite increasing sequence {(n_k)_{k=1}^\infty} and a color {t\in[r]} such that {t_{n_k}=t} for all {k\in{\mathbb N}}. Thus for any pair {k>j} we have that

\displaystyle x_{n_k}=\min S_{n_k}\subset S_{n_k-1}\subset\cdots\subset S_{n_j}+1

and hence {\chi\big(\{x_{n_j},x_{n_k}\}\big)=t}. This means that taking {S=\{x_{n_k}:k\in{\mathbb N}\}} we have that {\binom S2} is monochromatic.

\Box

We can now bootstrap this argument to prove the general case of Theorem 3 (with any {m\in{\mathbb N}}).

Proof:

We proceed by induction on {m}, the case {m=2} having been proved above (and the case {m=1} being the pigeonhole principle). Now assume that {m>2} and, for each {n\in{\mathbb N}}, let {\chi_n:\binom{{\mathbb N}\setminus[n]}{m-1}\rightarrow[r]} be the coloring defined by {\chi_n(a)=\chi(\{n\}\cup a)} for any {a\in\binom{{\mathbb N}\setminus[n]}{m-1}}.

Applying the induction hypothesis, there exists an infinite set {S_1\subset{\mathbb N}\setminus\{1\}} such that {\binom{S_1}{m-1}} is monochromatic with respect to {\chi_1}. This means that the family

\displaystyle \left\{\{1\}\cup a:a\in\binom{S_1}{m-1}\right\}

is monochromatic with respect to {\chi}.

Now we let {x_0=1} and create inductively a sequence {x_n=\min S_n} and an infinite set {S_{n+1}\subset S_n\setminus\{x_n\}} such that the family

\displaystyle \left\{\{x_n\}\cup a:a\in\binom{S_{n+1}}{m-1}\right\}\ \ \ \ \ (2)

is monochromatic for {n\in{\mathbb N}}.

Let {t_n\in[r]} be the color of the family (2). Applying the pigeonhole again we can find an infinite increasing sequence {(n_k)_{k=1}^\infty} and a color {t\in[r]} such that {t_{n_k}=t} for all {k\in{\mathbb N}}. Let {S=\{x_{n_k}:k\in{\mathbb N}\}}; we claim that {\binom Sm} is monochromatic (with color {t}).

Indeed, let {a\in\binom Sm} and let {x_{n_k}=\min a}. Then each of the elements of {a} different than {x_{n_k}} are of the form {x_n} for some {n>n_k}. This means that {b:=a\setminus\{x_{n_k}\}\in\binom{S_{n_k+1}}{m-1}}. We conclude that {\chi(a)=\chi\big(\{x_{n_k}\}\cup b\big)=t}. \Box

Analyzing the proof we see that Theorem 3 with {m=2} 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 {m=2}.

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 {S} together with all the sums of finite subsets of {S}. 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 {{\mathbb N}} is itself an IP-set, generated by {S=\{2^n:n\in{\mathbb N}\}}, because every natural number is the sum of some distinct powers of {2}. Because this representation is unique, Theorem 4 is equivalent to the fact that any finite coloring of {{\mathbb N}} contains a monochromatic IP-set.

When talking about IP-sets it is usually convenient to introduce the symbol {{\cal F}} to the denote the family of all finite non-empty subsets of {{\mathbb N}}. Thus if {(x_n)_{n\in{\mathbb N}}} is an increasing sequence and {x_\alpha=\sum_{n\in\alpha}x_n} for each {\alpha\in{\cal F}}, the IP-set generated by {S=\{x_n:n\in{\mathbb N}\}} is the set {\{x_\alpha:\alpha\in{\cal F}\}}.

It is trivial that {x_{\alpha\cup\beta}=x_\alpha+x_\beta} for any disjoint {\alpha,\beta\in{\cal F}} and indeed if {(y_\alpha)_{\alpha\in{\cal F}}} is any “sequence” indexed by {{\cal F}} such that {x_{\alpha\cup\beta}=x_\alpha+x_\beta} for any disjoint {\alpha,\beta\in{\cal F}}, then the set {\{y_\alpha:\alpha\in{\cal F}\}} is an IP-set (generated by {S=\{y_{\{n\}}:n\in{\mathbb N}\}}). For this reason we can refer to a generic IP-sets as {(y_\alpha)_{\alpha\in{\cal F}}}, generated by the sequence {(y_n)_{n\in{\mathbb N}}} where {y_n=y_{\{n\}}}. We will always assume that a sequence {(y_n)_{n\in{\mathbb N}}} generating an IP-set {(y_\alpha)_{\alpha\in{\cal F}}} 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 {(x_\alpha)_{\alpha\in{\cal F}},(y_\alpha)_{\alpha\in{\cal F}}} be IP-sets.

  • For {\alpha,\beta\in{\cal F}} we write {\alpha<\beta} as a shortcut to {\max\alpha<\min\beta}.
  • We say that {(x_\alpha)_{\alpha\in{\cal F}}} is a sub-IP of {(y_\alpha)_{\alpha\in{\cal F}}} if there exist {\alpha_1<\alpha_2<\cdots} such that {x_n=y_{\alpha_n}} for all {n\in{\mathbb N}}.

Equivalently, a sub-IP {A} of an IP-set {B} generated by an infinite set {S} (so that {B} contains {S} and all the sums of finite subsets of {S}) is the IP-set generated by a set {R} of the form

\displaystyle R=\left\{\sum_{k\in S_i}k:i\in{\mathbb N}\right\}

and {S_1<S_2<\dots} are finite subsets of {S} (and so {A} contains {R} together with all the sums of finite subsets of {R}).

It will be convenient to consider a particular type of sub-IPs.

Definition 6 (Shifted IP-sets) Let {(y_\alpha)_{\alpha\in{\cal F}}} be an IP-set generated by {(y_n)_{n\in{\mathbb N}}} and let {k\in{\mathbb N}}. Then we denote by {(y^{\rightarrow k}_\alpha)_{\alpha\in{\cal F}}} the sub-IP of {(y_\alpha)_{\alpha\in{\cal F}}} generated by the sequence {(y_{n+k})_{n\in{\mathbb N}}}.

Thus a shifted IP-set is just the tail of the original IP-set, after losing the first {k} generators.

— 3. Milliken-Taylor —

Definition 7 Let {(y_\alpha)_{\alpha\in{\cal F}}} be an IP-set and let {m\in{\mathbb N}}. We define {MT(y,m)\subset\binom{\mathbb N} m} to be the family of the {m}-tuples {\{y_{\alpha_1},\dots,y_{\alpha_m}\}} such that {\alpha_1<\cdots\alpha_m}.

Theorem 8 (Milliken-Taylor) For any {m\in{\mathbb N}}, any IP-set {(y_\alpha)_{\alpha\in{\cal F}}} and any finite coloring of {MT(y,m)}, there exists a sub-IP {(x_\alpha)_{\alpha\in{\cal F}}} of {(y_\alpha)_{\alpha\in{\cal F}}} such that {MT(x,m)} 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 {r\in{\mathbb N}} and let {\chi:MT(y,m)\rightarrow[r]} be arbitrary. Passing, if necessary to a sub-IP we can (and will) assume that {y_\alpha\neq y_\beta} for {\alpha\neq\beta}.

We proceed by induction on {m}, the case {m=1} being Hindman’s theorem. Now assume that {m>1} and that the result has been established for {m-1}.

Let {\chi_1:MT(y^{\rightarrow1},m-1)\rightarrow[r]} be defined by {\chi_1(a)=\chi({y_1}\cup a)}. Applying the induction hypothesis, there exists a sub-IP {(z_\alpha^{(1)})_{\alpha\in{\cal F}}} of {(y^{\rightarrow1}_\alpha)_{\alpha\in{\cal F}}} such that {MT(z^{(1)},m-1)} is monochromatic with respect to {\chi_1}. This means that the family

\displaystyle \left\{\{y_1\}\cup a:a\in MT(z^{(1)},m-1)\right\} \ \ \ \ \ (3)

is monochromatic with respect to {\chi}.

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 {\chi_2:MT(z^{(1),\rightarrow1},m-1)\rightarrow[r]^2} be defined by

\displaystyle \chi_2(a)=\left(\chi\big(\{z_1^{(1)}\cup a\}\big),\chi\big(\{y_1+z_1^{(1)}\cup a\}\big)\right)\qquad\forall a\in MT(z^{(1),\rightarrow1},m-1)

Applying the induction hypothesis, there exists a sub-IP {(z_\alpha^{(2)})_{\alpha\in{\cal F}}} of {(z^{(1),\rightarrow1}_\alpha)_{\alpha\in{\cal F}}} such that {MT(z^{(2)},m-1)} is monochromatic with respect to {\chi_2}. This means that both families

\displaystyle \left\{\{z^{(1)}_1\}\cup a:a\in MT(z^{(2)},m-1)\right\}

and

\displaystyle \left\{\{y_1+z^{(1)}_1\}\cup a:a\in MT(z^{(2)},m-1)\right\}

are monochromatic with respect to {\chi}, although possibly of different colors.

Now let {z_1=y_1}, {z_2=z_1^{(1)}} and {z_3=z_1^{(2)}}. In the next lemma we summarize the induction step:

Lemma 9 There exist IP-sets {(z_\alpha^{(n)})_{\alpha\in{\cal F}}} such that for each {n\in{\mathbb N}}:

  • {(z_\alpha^{(n)})_{\alpha\in{\cal F}}} is a sub-IP of {(z_\alpha^{(n-1),\rightarrow1})_{\alpha\in{\cal F}}}
  • Putting {z_n=z_1^{(n-1)}} we have

    \displaystyle \left\{\{z_\gamma\}\cup a:a\in MT(z^{(n)},m-1)\right\}\ \ \ \ \ (4)

    is monochromatic for every {\gamma\subset[n]} with {n\in\gamma}.

Proof: Assume the IP-sets {(z_\alpha^{(k)})_{\alpha\in{\cal F}}} have been found for all {k<n}. Define the coloring {\chi_n:MT(z^{(n-1),\rightarrow1},m-1)\rightarrow[r]^{2^{n-1}}} by letting

\displaystyle \chi_n(a)=\left(\chi\Big(\big\{z_\gamma+z_1^{(n-1)}\big\}\cup a\Big)\right)_{\gamma\subset[n-1]}\in[r]^{2^{n-1}}

Applying the induction hypothesis we can now extract a sub-IP {(z_\alpha^{(n)})_{\alpha\in{\cal F}}} of {(z_\alpha^{(n-1),\rightarrow1})_{\alpha\in{\cal F}}} such that {MT(z^{(n)},m-1)} is monochromatic with respect to {\chi_n}. However, that means that (4) is monochromatic whenever {\gamma\subset[n]} contains {n}. \Box

Let {z_n=z_1^{(n-1)}} as in the lemma. Observe that, for each {\alpha\in{\cal F}}, Lemma 9 implies that the family

\displaystyle \left\{\{z_\alpha\}\cup a:a\in MT(z^{\rightarrow s},m-1)\right\}\ \ \ \ \ (5)

is monochromatic, where {s=\max\alpha}. Define the coloring {\tilde\chi:\{z_\alpha:\alpha\in{\cal F}\}\rightarrow[r]} by assigning to {\alpha\in{\cal F}} the color {\tilde\chi(z_\alpha)} of the family (5). By Hindman theorem there exists a sub-IP {(x_\alpha)_{\alpha\in{\cal F}}} of {(z_\alpha)_{\alpha\in{\cal F}}} monochromatic under {\tilde\chi}. By construction we have that the color of the family

\displaystyle \Big\{\{x_\alpha\}\cup a:a\in MT(x^{\rightarrow s},m-1)\Big\}

does not depend on {\alpha}. This is equivalent to say that {MT(x,m)} is monochromatic as desired. \Box

An interesting corollary of this result arises by making the color of a set {a\in\binom{\mathbb N} m} depend only on the sum {\sum_{k\in a}k}, or more generally on some fixed linear combination of the elements of {a}.

Definition 10 Let {m\in{\mathbb N}}, let {c_1,\dots,c_m\in{\mathbb N}} and let {(x_\alpha)_{\alpha\in{\cal F}}} be an IP-set. We define

\displaystyle \tilde{MT}(x,c_1,\dots,c_m):=\left\{\sum_{i=1}^mc_ix_{\alpha_i}:\alpha_1<\cdots<\alpha_m\right\}

Corollary 11 Let {r,m,c_1,\dots,c_m\in{\mathbb N}} and let {(y_\alpha)_{\alpha\in{\cal F}}} be an IP-set. For any coloring {\chi:\tilde{MT}(y,c_1,\dots,c_m)\rightarrow[r]} there exists a sub-IP {(x_\alpha)_{\alpha\in{\cal F}}} of {(y_\alpha)_{\alpha\in{\cal F}}} such that {\tilde{MT}(x,c_1,\dots,c_m)} is monochromatic.

Proof: Let {\tilde\chi:MT(y,m)\rightarrow[r]} be given by

\displaystyle \tilde\chi(y_{\alpha_1},\dots,y_{\alpha_m})=\chi\left(\sum_{i=1}^mc_iy_{\alpha_i}\right)\qquad\forall\alpha_1<\cdots<\alpha_m

Applying Milliken-Taylor’s Theorem 8 we find a sub-IP {(x_\alpha)_{\alpha\in{\cal F}}} of {(y_\alpha)_{\alpha\in{\cal F}}} such that {MT(x,m)} is monochromatic with respect to {\tilde\chi}. This implies that {\tilde{MT}(x,c_1,\dots,c_m)} is monochromatic with respect to {\chi} as desired. \Box

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 {x_n>(c_1+\cdots+c_m)(x_1+\cdots+x_{n-1})} for all {n}. This implies that there is a bijection between {MT(y,m)} and {\tilde{MT}(y,c_1,\dots,c_m)}), and so both versions are equivalent.

Advertisements

About Joel Moreira

PhD Student at OSU in Mathematics. I'm portuguese.
This entry was posted in Combinatorics, Ramsey Theory and tagged , , , , , . Bookmark the permalink.

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