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 colors 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 -coloring of the edges of a graph we mean any function with domain and range which induces such a partitioning. The colors are the labels that we may use for this partitioning.
Theorem: Let be the complete infinite graph with vertices . Given any -coloring of the edges, 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 have been colored using the colors . We will build an infinite subsequence of the vertices in by applying the infinite pigeonhole principle. Let . Now is connected with every other vertex in and the edges making this connection are colored in any of -ways. We partition the set of all these vertices in this fashion: If is connected to via an edge colored we consider it to be a member of the set . Clearly, is a partitioning of . Now, since is infinite so one of the must also be infinite. (Here we are using the infinite pigeonhole principle.) Note that there may be more then one infinite . At any rate choose the “smallest” vertex among the infinite parts (or the vertex with the least in is infinite . Rename that particular as and that vertex as .
At this point the construction of the sequence becomes obvious. If for some we have already found a and and a then we can partition the vertices in connected to into -parts depending on how they are connected with . Choosing the smallest vertex among the infinite parts yields and the part it belongs to yields . Since is infinite so we have no fear of running out of vertices.
Now note an important property of the sequence . Given any its connections with are all of the same color by definition. Let us call as -based if the edges are all colored . The fact that all the members of the sequence are based in any of -ways induces a partitioning of the sequence . 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 of in which all vertices are the same color base, say . It is now easy to observe that the subgraph induced by these vertices has all edges colored , which proves the theorem.
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 be natural numbers. Then there exists an such that any -coloring of contains a monochromatic for some entirely colored in color .
We will prove the theorem with . This is because no loss of generality occurs by assuming this. To see this suppose and . Now if we have proved the theorem for we have also guaranteed the existence of an such that any -coloring of contains a colored in either of the two colors. Clearly the same works for as a -colored would contain a -colored .
Proof: Our modified claim is that for all there is an such that any -coloring of contains a monochromatic . By way of contradiction assume that there is an such that for every there is a -coloring of containing no monochromatic . Now let be a complete graph with vertices and let the edges of be enumerated by . We construct a (rooted) tree as follows:
1. First introduce a root vertex .
2. Each vertex is allowed to have at most children (a child of a vertex is defined to be an adjacent vertex so that ) which correspond to the -colors, subject to it satisfying the criteria below. A child is always labeled by one among the -colors. (Call the colors for convenience).
3. A child is permitted if and only if its introduction creates a path of some finite length starting from the root, so that if the edges are colored by the colors used in the path in the same order, then the corresponding subgraph in does not contain a monochromatic . For example if the introduction of a child creates the length path and the edges when colored don’t contain a monochromatic the child is permitted to be added to .
Note that for all , there always exists a coloring of such that no monochromatic exists within. So the situation that a child cannot be added to any vertex at a given level cannot arise. For we can always take a coloring of containing no monochromatic . Since any edges in it would yield a sequence of colors already existing in , 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 is infinite. It is also obvious that each level of has at most vertices and so each level is finite.
Now by Konig’s lemma there will be an infinite path in . This infinite path provides a -coloring of 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.