# 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$