Tag Archives: Ramsey theory

On unabridged versions of Ramsey’s theorem

In continuation of our discussions on Ramsey theory in this post we plan to prove the unabridged versions of Ramsey’s theorem. While the abridged versions dealt with graphs, unabridged versions deals with hypergraphs. A hypergraph, is a set of vertices V together with a set of subsets of V of a fixed order n. If n=2 then we get back the ordinary definition of a graph.

An example of a hypergraph of order 3 is given below:

The vertex set V=\{a,b,c,d,e\} and the hyperedges are given by: \{a,b,c\}, \{b,d,e\} and \{a,b,d\}.

The infinite unabridged version of Ramsey’s theorem may now be described as follows: Given a complete infinite hypergraph of order n with vertex set \mathbb{N}, and a r-coloring of its hyperedges we are guaranteed a infinite complete monochromatic subgraph.

Let us try to express this more succinctly. We will extend the previously defined arrows notation as follows: The notation \alpha\rightarrow (\beta)^n_r will mean that every r-colored complete hypergraph of order n on \alpha vertices contains a monochromatic complete subgraph with \beta vertices. Since hypergraphs do not seem to be as picturesque as graphs, so maybe the idea will be better expressed in terms of sets: \alpha\rightarrow (\beta)^n_r equivalently means that for any assignment of r-colors to the n-subsets of \alpha, there is a particular color (say red) and a subset X of \alpha of size \beta such that all n-subsets of X are red. (Note that \alpha,\beta etc can be any cardinal numbers.)

With the notation that \omega stands for the cardinality of \mathbb{N} the infinite version of Ramsey’s theorem now is:

Theorem: \forall n,r\in\mathbb{N}, \omega\rightarrow(\omega)^n_r.

The proof is essentially on the same lines as in the abridged case, with the addition that we induct on n. (n may intuitively be thought of as the “hyper-ness” of our hypergraph.)

Proof: By induction on n. If n=1 we just get the infinite pigeonhole principle: Any finite partitioning of \mathbb{N} contains an infinite part. Indeed, both the infinite and finite Ramsey theorems may be thought of as gigantic generalizations of the pigeonhole principle.

Now suppose that for a fixed n,r we have \omega\rightarrow(\omega)^n_r. Now consider any r-coloring f of the n+1-subsets of \omega. Just like in the proof of the abridged case we build a sequence (w_k). In the abridged case we applied the infinite pigeonhole principle repeatedly at this point. Here we will use the induction hypothesis repeatedly. Let w_1=1. Consider the r-coloring f_{w_1} of all n-subsets of \omega-\{1\} given by f_{w_1}(X)=f(\{1\}\cup X). By the induction hypothesis there will be a countable subset of \omega whose all n-subsets will be monochromatic. Call that subset V_1. Let the least element of V_1 be designated as w_2.

The construction of (w_k) follows by induction: If the set V_k and its least element w_{k+1} have been found, consider the r-coloring f_{w_{k+1}} of the n-subsets of V_k given by f_{w_{k+1}}(X)=f(\{w_{k+1}\}\cup X). By the induction hypothesis it contains a countable set all of whose n-subsets are monochromatic. Call that subset V_{k+1}. Its least element is designated as w_{k+2}.

The sequence (w_k) has the property that given any w_i the union of \{w_i\} with any n-order subset containing elements from w_{i+1},w_{i+2},w_{i+3}\cdots has the same color (with respect to the the original coloring f). Let us call w_i as c_j-based if this color is c_j. The fact that all the members of the sequence (w_k) are based in any of r-ways induces a partitioning of the sequence (w_k). By the infinite pigeonhole principle we are guaranteed an infinite part. Now, by ordering the terms appropriately in this infinite part we have a subsequence (w_{k_j}) of (w_k) in which all vertices are the same color base, say c_1. It is now easy to observe that all the n+1-subsets of this infinite part are colored c_1, which proves the theorem.\Box

We now turn to the finite version. In our arrows notation, the natural generalization from the abridged analogue reads:

Theorem: \forall l,n,r\in\mathbb{N}, \exists m\in\mathbb{N} such that m\rightarrow (l)_r^n.

Proof: The proof is identical to the abridged case with cosmetic changes. By way of contradiction assume that there is an l such that for all m\in\mathbb{N} we have m\nrightarrow (l)_r^n. We will use the notation \hat{K_i} for a hypergraph on i vertices where all possible n-subsets of the vertices are the hyperedges. Also let G be a hypergraph with vertices V=\{v_i:i\in\mathbb{N}\} and let the hyperedges of G be enumerated by E=\{E_i:E_i\subset\mathbb{N}, |E_i|=n\}. We construct a (rooted) tree T as follows:

1. First introduce a root vertex rt.

2. Each vertex is allowed to have at most r children which correspond to the r-colors, subject to it satisfying the criteria below. A child is always labeled by one among the r-colors. (Call the colors c_1,c_2\cdots c_r for convenience).

3. A child c_i is permitted if and only if its introduction creates a path of some finite length k starting from the root, so that if the hyperedges E_1,E_2\cdots E_k are colored by the colors used in the path in the same order, then the corresponding subgraph in G does not contain a monochromatic \hat{K_l}. For example if the introduction of a child c_i creates the k length path rt,c_a,c_b\cdots ,c_i and the hyperedges E_1,E_2,\cdots E_k when colored c_a,c_b\cdots c_i don’t contain a monochromatic \hat{K_l} the child c_i is permitted to be added to T.

Note that for all m, there always exists a coloring of \hat{K_m} such that no monochromatic \hat{K_l} exists within. So the situation that a child cannot be added to any vertex at a given level k cannot arise. For we can always take a coloring of \hat{K_{k+n}} containing no monochromatic \hat{K_l}. Since any k hyperedges in it would yield a sequence of colors already existing in T, we know which vertex to add the child to. We give the child the color corresponding to any other edge. Hence we can forever keep adding children and so T is infinite. It is also obvious that each level k of T has at most r^k vertices and so each level is finite.

Now by Konig’s lemma there will be an infinite path in T. This infinite path provides a r-coloring of G that contains no monochromatic \hat{K_i} and hence no monochromatic infinite hypergraph which contradicts the infinite Ramsey theorem proved above. This contradiction proves the theorem.\Box

The astute reader may have noted that we have used weak versions of the axiom of choice occasionally in the proof. Ramsey himself was aware of this and remarked so in his original paper. In fact, it can be proved that Ramsey’s theorem cannot ever be proved without using some form of the axiom of choice. Moreover it can be shown that a weak form of the axiom of choice is equivalent to Ramsey’s theorem. Hence Ramsey’s theorem may be interpreted as a choice axiom.

Advertisements

1 Comment

Filed under Combinatorics, Graph theory, Ramsey theory

Arrows, Ramsey numbers and the Party Problem

Here come the arrows! The notation \alpha\rightarrow (\beta)^2_r means that every r-colored complete graph on \alpha vertices contains a monochromatic complete subgraph with \beta vertices. Using the notation \omega for the cardinality of the natural numbers the abridged Ramsey theorems state that \omega\rightarrow (\omega)^2_r and that \forall n\exists m,m\rightarrow (n)^2_r.

Now let us take a particular case: n=3,r=2. Our objective here is to prove that 6\rightarrow (3)^2_2. In other words, if the edges of K_6 are 2-colored then there exists a monochromatic K_3. Fix a vertex v in K_6. From the 5 edges emanating from v, at least three must share a color: call it c. Now if all the edges in triangle made by those three vertices are not colored c, we are done for we have found a monochromatic K_3 in the other color. If even one edge, say xy among the triangle made by those three vertices is of color c then we have a monochromatic K_3 colored c with vertices x,y and v.

The fact that 6\rightarrow (3)^2_2 is also referred to as the solution of the party problem: Prove that in any gathering of six people there are three mutual friends, or three mutual strangers. By representing the people as vertices and their relationships via the colors on the edges connecting them we easily see that a monochromatic triangle is guaranteed and therefore the result holds. It is also obvious that the gathering may contain more then six people, a monochromatic triangle is still guaranteed within (in fact, it will only become more likely with more people). In other words: m\rightarrow (3)^2_2\forall m\ge 6.

Is six the least such number? Indeed it is as the following graph demonstrates:

We note that there is no monochromatic triangle in the above 2-colored K_5.

For a given n the least such number m,m\rightarrow (n)^2_r is called the diagonal Ramsey number R(n,n). While such numbers are guaranteed to exist by Ramsey’s theorem, actually finding them is hard indeed. It is trivial to see that R(1,1)=1 and R(2,2)=2. Our proof above illustrates that R(3,3)=6. It has also been proven that R(4,4)=18. However all efforts to find out the exact value of any other diagonal Ramsey number have failed. It is one of those problems, which are easily stated but extremely difficult to attack.

Regarding R(5,5), Joel Spencer comments in his book, Ten lectures on the Probabilistic Method:

Erdős asks us to imagine an alien force, vastly more powerful than us, landing on Earth and demanding the value of R(5,5) or they will destroy our planet. In that case, he claims, we should marshal all our computers and all our mathematicians and attempt to find the value. But suppose, instead, that they ask for R(6,6). In that case, he believes, we should attempt to destroy the aliens.

In closing it may be remarked that the Ramsey number R(m,n) is defined to be the least positive integer such that any 2-coloring of K_{R(m,n)} in two colors, say red and blue, contains either a red K_m or a blue K_n. This definition also has the natural generalization for more then two colors. Although the existence of all Ramsey numbers is guaranteed by Ramsey’s theorem, only few have been discovered so far.

1 Comment

Filed under Combinatorics, Miscellaneous, Ramsey theory

On abridged versions of Ramsey’s theorem

This post will aim to prove two abridged versions of Ramsey’s theorem, the result which gave its name to the area of mathematics now known as Ramsey theory. Ramsey theory may be understood as ramifications of a philosophical principal. The principle may be summarized as: “Complete disorder is an impossibility. Any structure will necessarily contain an orderly substructure.” Ramsey’s theorem is an example of this principle. Van der Waerden’s theorem is another example.

First a bit of history regarding this theorem. Frank Ramsey, a 25 year old British mathematician, proved this result in 1928 as a part of his investigations in mathematical logic. Unfortunately he passed away in 1930 (even before his theorem was formally published) and did not prove anything else related to this. In 1933, Skolem published another proof of the theorem, and then in 1934, Erdos and Szekeres found yet another. It was the Erdos and Szekeres paper which gave Ramsey’s theorem a wide audience. Further work by Erdos in this area led mathematicians to consider other Ramsey type theorems.

Here we consider abridged versions of Ramsey’s theorem which can be easily understood in the context of graphs. We will imitate Ramsey’s original approach (though not his proof) to first prove an infinite version (which deals with infinite graphs) and then proceed towards the finite analogue.

So what is the infinite version. Briefly it says that if we have an infinite complete graph on countable vertices and if we use r colors c_1,c_2\cdots c_r to arbitrarily color the edges then we are guaranteed an infinite monochromatic subgraph. Here our usage of coloring an edge is just a fanciful way to describe partitioning the edge set into finitely many parts. More formally, by a r-coloring of the edges of a graph G we mean any function with domain E(G) and range \{1,2\cdots r\} which induces such a partitioning. The colors are the labels that we may use for this partitioning.

Theorem: Let G be the complete infinite graph with vertices V=\{v_i:i\in\mathbb{N}\}. Given any r-coloring of the edges, G will contain an infinite complete monochromatic subgraph.

Ramsey’s original formulation was more general. He considered the set of vertices to be any infinite set (and not just countable). That is not much gained because a coloring of an uncountable vertex graph induces a coloring of a countable vertex subgraph. Within this countable subgraph we can find a monochromatic infinite complete graph, which is also a subgraph of the original. However he also generalized in another sense: Instead of coloring edges he considered colorings of hyperedges of a fixed order (an edge is a special case: it is a hyperedge of order 2). This too can be overcome by induction on the “hyper-ness” of the graph. We choose to postpone such discussions.

Proof: Suppose the edges of G have been colored using the colors c_1,c_2,\cdots c_r. We will build an infinite subsequence of the vertices in V by applying the infinite pigeonhole principle. Let w_1=v_1. Now w_1 is connected with every other vertex in G and the edges making this connection are colored in any of r-ways. We partition the set of all these vertices in this fashion: If v is connected to w_1 via an edge colored c_i we consider it to be a member of the set P_i. Clearly, \{P_i:i=1,2\cdots r\} is a partitioning of V-\{w_1\}. Now, since \cup P_i is infinite so one of the P_i must also be infinite. (Here we are using the infinite pigeonhole principle.) Note that there may be more then one infinite P_i. At any rate choose the “smallest” vertex among the infinite parts (or the vertex with the least i in \{v_i:i\in P_j, P_j is infinite \}. Rename that particular P_i as V_1 and that vertex as w_2.

At this point the construction of the sequence becomes obvious. If for some n we have already found a w_n and and a V_n then we can partition the vertices in V_n connected to w_n into r-parts depending on how they are connected with w_n. Choosing the smallest vertex among the infinite parts yields w_{n+1} and the part it belongs to yields V_{n+1}. Since V_{n+1} is infinite so we have no fear of running out of vertices.

Now note an important property of the sequence (w_n). Given any w_i its connections with w_{i+1},w_{i+2},w_{i+3}\cdots are all of the same color by definition. Let us call w_i as c_j-based if the edges w_iw_{i+1},w_iw_{i+2},w_iw_{i+3}\cdots are all colored c_j. The fact that all the members of the sequence (w_n) are based in any of r-ways induces a partitioning of the sequence (w_n). As before by the pigeonhole principle we are guaranteed an infinite part. Now, by ordering the terms appropriately in this infinite part we have a subsequence (w_{n_k}) of (w_n) in which all vertices are the same color base, say c_1. It is now easy to observe that the subgraph induced by these vertices has all edges colored c_1, which proves the theorem.\Box

We now turn our attention to the finite analogue. The infinite version guarantees an infinite monochromatic complete graph within an arbitrarily colored infinite countable graph (with countable vertices). The finite version guarantees a finite monochromatic complete graph of desired size within an arbitrarily colored finite countable graph (with suitable number of vertices). More formally the theorem states:

Theorem: Let r,l_1,l_2,\cdots l_r be natural numbers. Then there exists an m\in \mathbb{N} such that any r-coloring of K_m contains a monochromatic K_{l_i} for some i entirely colored in color i.

We will prove the theorem with l_1=l_2=\cdots =l_r=n. This is because no loss of generality occurs by assuming this. To see this suppose r=2,l_1=5 and l_2=7. Now if we have proved the theorem for r=2,l_1=l_2=7 we have also guaranteed the existence of an m such that any 2-coloring of K_m contains a K_7 colored in either of the two colors. Clearly the same m works for l_1=5,l_1=7 as a 1-colored K_7 would contain a 1-colored K_5.

Proof: Our modified claim is that for all r,n\in\mathbb{N} there is an m\in\mathbb{N} such that any r-coloring of K_m contains a monochromatic K_n. By way of contradiction assume that there is an n\in\mathbb{N} such that for every m\in \mathbb{N} there is a r-coloring of K_m containing no monochromatic K_n. Now let G be a complete graph with vertices V=\{v_i:i\in\mathbb{N}\} and let the edges of G be enumerated by E=\{e_i:i\in\mathbb{N}\}. We construct a (rooted) tree T as follows:

1. First introduce a root vertex rt.

2. Each vertex is allowed to have at most r children (a child of a vertex x is defined to be an adjacent vertex y so that d(rt,x)+1=d(rt,y)) which correspond to the r-colors, subject to it satisfying the criteria below. A child is always labeled by one among the r-colors. (Call the colors c_1,c_2\cdots c_r for convenience).

3. A child c_i is permitted if and only if its introduction creates a path of some finite length k starting from the root, so that if the edges e_1,e_2\cdots e_k are colored by the colors used in the path in the same order, then the corresponding subgraph in G does not contain a monochromatic K_n. For example if the introduction of a child c_i creates the k length path rt,c_a,c_b\cdots ,c_i and the edges e_1,e_2,\cdots e_k when colored c_a,c_b\cdots c_i don’t contain a monochromatic K_n the child c_i is permitted to be added to T.

Note that for all m, there always exists a coloring of K_m such that no monochromatic K_n exists within. So the situation that a child cannot be added to any vertex at a given level k cannot arise. For we can always take a coloring of K_k containing no monochromatic K_n. Since any k edges in it would yield a sequence of colors already existing in T, we know which vertex to add the child to. We give the child the color corresponding to any other edge. Hence we can forever keep adding children and so T is infinite. It is also obvious that each level k of T has at most r^k vertices and so each level is finite.

Now by Konig’s lemma there will be an infinite path in T. This infinite path provides a r-coloring of G that contains no monochromatic complete graph and hence no monochromatic infinite complete graph which contradicts the infinite Ramsey theorem proved above. This contradiction proves the theorem.\Box

3 Comments

Filed under Combinatorics, Graph theory, Ramsey theory

The van der Waerden theorem

In this post I aim to prove van der Waerden’s theorem on arithmetic progressions.

The theorem states that \forall k,r\in\mathbb{N}\exists W(k,r)\in\mathbb{N} so that if the set \{1,2\cdots W(k,r)\} is partitioned into r classes, one of the classes is guaranteed to contain an arithmetic progression of length k.

Before proceeding further, lets look at a bit of history regarding this result. As per a recent book the theorem was conjectured independently by the mathematicians Schur and Baudet sometime around the 1920’s. (The exact dates are unknown). In 1926 van der Waerden, then a young scholar in Hamburg, heard of this conjecture (he believed it to be solely by Baudet) and proved it in the course of a remarkable discussion with his teacher Emil Artin and the mathematician Otto Schreier. The beauty of the proof was that it did not use any tools of advanced mathematics and yet was not simple by any means. Khinchin has referred to it as one of the three pearls of number theory.

Our proof here is not the same proof as originally given by van der Waerden, but a slightly slicker version based on the same idea. We start by making some preparations for the proof. For convenience we will take [n]=\{1,2\cdots n\}. Further we can very well uniquely identify a partitioning \{W_1,W_2,\cdots W_r\} of a set [W(k,r)]=\cup_{i=1}^rW_i by a function f with domain [W(k,r)] and range [r] where f^{-1}(i) equals W_i. Traditionally the numbers \{1,2\cdots r\} are called colors, every such function is called a r-coloring and the sets f^{-1}(i) are referred to as being colored i. Given a r-coloring a subset of [W(k,r)] is called monochromatic if every element in it corresponds with the same color. With these new definitions the van der Waerden theorem takes the form:

Theorem: \forall k,r\in\mathbb{N}\exists W(k,r)\in\mathbb{N} so that if [W(k,r)] is r-colored then there is a monochromatic arithmetic progression of length k.

We shall also use the notation a + [0,k)d for the arithmetic progression of length k (also abbreviated as a k-AP) given by the ordered set \{a<a+d<a+2d<\cdots a+(k-1)d\}

And now, on to the proof. As a first step towards proving the result we shall first introduce the concept of wheels. The next step will establish some technical lemmas concerning them and after that we will prove the van der Waerden theorem.

A wheel of radius k, degree n and base point or origin a is a n tuple: W= (a + [0,k) d_1,\cdots, a + [0,k)d_n) of k-AP's each of which has base point a. The AP's a + [1,k)d_i, 1 \le i \le n are called the spokes of the wheel. Assuming that all numbers under consideration have been colored a wheel is weakly polychromatic if all of it’s n spokes are monochromatic with distinct colors, and strongly polychromatic if it’s n spokes and origin are all monochromatic with distinct colors.

An example of a strongly polychromatic wheel of degree 8 and radius 5 is given below. In case of a weakly polychromatic wheel the origin, i.e. 1, can be of any of the colors of the spokes.

The 8 AP’s are:
1,2,3,4,5
1,10,19,28,37
1,4,7,10,13
1,7,13,19,25
1,6,11,16,21
1,8,15,22,29
1,5,9,13,17
1,3,5,7,9

A translation of a wheel W by a number r defined as the wheel obtained by adding a to each number in W.

We now move on to the next stage in our proof, where we shall establish some technical lemmas concerning wheels.

Lemma 1: If W= (a + [0,k) r_1,\cdots, a + [0,k)r_n) is a wheel of radius k and degree n and the k-1 translations W + r ,\cdots W+(k-1)r of W are all strongly polychromatic with the same colors, then the wheel \hat{W} = (a + [0,k)r , a + [0,k)(r_1 + r),\cdots a + [0,k)(r_n + r)) of radius k and degree n+1 is weakly polychromatic.

Proof: The integers a + (r_i + r), a + 2(r_i + r), \cdots a + (k-1)(r_i + r) respectively picked from W+r, W + 2r ,\cdots  W+(k-1)r are identical in color because the ith component of each translation is colored identically. So \forall i, 1 \le i \le n, a + [1,k)(r_i + r) is monochromatically colored and distinct from others. Similarly the AP of the base points a+r,a+2r,\cdots a+(k-1)r also has a distinct color. Thus we have a n+1 tuple of AP’s each of which is distinctly monochromatic if we ignore the base point a, or that \hat{W} is weakly polychromatic.

Two more lemmas whose proofs are obvious are:

Lemma 2: If W is a weakly polychromatic wheel of radius k, then either W is strongly polychromatic, or contains a monochromatic AP of length k.

Lemma 3: A strongly polychromatic wheel cannot have degree r where r is the total number of colors.

With the necessary machinery in our arsenal we now attack the van der Waerden theorem proper.

Proof of the van der Waerden theorem: We shall use double induction. The first (outer) induction is on k. Clearly for k = 1,2 and any r the result holds. Let us suppose that W(k-1,r) exists for all r. Now we

Claim: For any n\in\mathbb{N},\exists N=N(k-1,r,n)\in\mathbb{N} such that given any r-coloring of [N], there exists either a monochromatic AP of length k, or there exists a strongly polychromatic wheel of radius k and degree n.

To prove the claim we use (an inner) induction on n. The case n = 1 is trivial if we use the outer induction hypothesis. Suppose the result holds for n-1, that is, N_1 = N(k-1,r,n-1) exists. Now by the inner hypothesis any block of integers of length N_1 contains either a monochromatic AP of length k (in which case we are done) or a strongly polychromatic wheel of radius k and degree n-1. In the second case let N_2 = 2W(k-1, r^{N_1}) which exists by the outer hypothesis, color the first N_1N_2 integers and consider N_2 consecutive blocks of length N_1. Since there are r^{N_1} colorings of each block, by the outer hypothesis there must be an AP of k-1 identically colored blocks: B+d, B+2d,\cdots B+(k-1)d.

Now as |B| = N_1 = N(k-1,r,n-1) so inside each block, there is either a monochromatic AP of length k in it, (which proves the theorem) or a strongly polychromatic wheel of radius k and degree n-1. Ruling out the former case means that each block B + d, \cdots B +(k-1)d contains a strongly polychromatic wheel of degree n-1. Since these blocks are identical in color so we have a AP of strongly polychromatic identical wheels. In this case, by lemma 1, the AP of blocks contains a weakly polychromatic wheel W of radius k and degree n. By lemma 2, W is either strongly polychromatic or contains a monochromatic AP of length k. In either case we have proved our claim.

The proof of van der Waerden’s theorem is trivial now. Choose W(k,r) = N(k-1,r,r). Now an r-coloring of [W(k,r)] contains either a monochromatic AP of length k or a strongly polychromatic wheel of degree r. The latter case is not possible due to lemma 3.\Box

1 Comment

Filed under Combinatorics, Ramsey theory