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



Filed under Combinatorics, Graph theory, Ramsey theory

3 responses to “On abridged versions of Ramsey’s theorem

  1. Pingback: Arrows, Ramsey’s theorem and the Party Problem | Notes on Mathematics

  2. Pingback: On unabridged versions of Ramsey’s theorem | Notes on Mathematics

  3. Pingback: Ramsey infinite | Questionhypoth

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