11.1: A First Taste of Ramsey Theory

Bob likes to think of himself as a wild and crazy guy, totally unpredictable. Most guys do. But Alice says that Bob can't change his basic nature, which is excruciatingly boring. Carlos remarks that perhaps we shouldn't be so hard on Bob, because under certain circumstances, we can all be forced to be dull and repetitive.

Recall that when \(n\) is a positive integer, we let \([n]=\{1,2,…,n\}\). In this chapter, when \(X\) is a set and \(k\) is a non-negative integer with \(k \leq |X|\), we borrow from our in-line notation for binomial coefficients and let \(C(X,k)\) denote the family of all \(k\)-element subsets of \(X\). So \(|C([n],k)|=C(n,k)\) whenever \(0 \leq k \leq n\).

Recall that the Pigeon Hole Principle asserts that if \(n+1\) pigeons are placed in \(n\) holes, then there must be some hole into which two or more pigeons have been placed. More formally, if \(n\) and \(k\) are positive integers, \(t>n(k−1)\) and \(f:[t] \rightarrow [n]\) is any function, then there is a \(k\)-element subset \(H⊆[t]\) and an element \(j \in [n]\) so that \(f(i)=j\) for every \(i \in H\).

We now embark on a study of an elegant extension of this basic result, one that continues to fascinate and challenge.

Returning to the discussion at the start of this section, you might say that an induced subgraph \(H\) of a graph \(G\) is “boring” if it is either a complete subgraph or an independent set. In either case, exactly every pair of vertices in \(H\) behaves in exactly the same boring way. So is boredom inevitable? The answer is yes—at least in a relative sense. As a starter, let's show that any graph on six (or more) vertices has a boring subgraph of size three.

Lemma 11.1

Let \(G\) be any graph with six of more vertices. Then either \(G\) contains a complete subgraph of size 3 or an independent set of size 3.

Proof

Let \(x\) be any vertex in \(G\). Then split the remaining vertices into two sets \(S_1\) and \(S_2\) with \(S_1\) being the neighbors of \(x\) and \(S_2\) the non-neighbors. Since \(G\) has at least six vertices, we know that either \(|S_1| \geq 3\) or \(|S_2| \geq 3\). Suppose first that \(|S_1| \geq 3\) and let \(y_1, y_2\) and \(y_3\) be distinct vertices from \(S_1\). If \(y_iy_j\) is an edge in \(G\) for some distinct pair \(i,j \in \{1,23\}\), then \(\{x,y_i,y_j\}\) is a complete subgraph of size 3 in \(G\). On the other hand, if there are no edges among the vertices in \(\{y_1,y_2,y_3\}\), then we have an independent set of size .3.

The argument when \(|S_2| \geq 3\) is dual.

We note that the bound of six in the preceding lemma is sharp, as a cycle on five vertices does not contain either a complete set of size 3 nor an independent set of size 3.

Next, here is the statement that generalizes this result.

Theorem 11.2. Ramsey's Theorem for Graphs

If \(m\) and \(n\) are positive integers, then there exists a least positive integer \(R(m,n)\) so that if \(G\) is a graph and \(G\) has at least \(R(m,n)\) vertices, then either \(G\) contains a complete subgraph on \(m\) vertices, or \(G\) contains an independent set of size \(n\).

Proof

We show that \(R(m,n)\) exists and is at most \(\binom{m+n-2}{m-1}\). This claim is trivial when either \(m \leq 2\) or \(n \leq 2\), so we may assume that \(m,n \geq 3\). From this point, we proceed by induction on \(t=m+n\) assuming that the result holds when \(t \leq 5\).

Now let \(x\) be any vertex in \(G\). Then there are at least \(\binom{m+n-2}{m-1}-1\) other vertices, which we partition as \(S_1 \cup S_2\), where \(S_1\) are those vertices adjacent to \(x\) in \(G\) and \(S_2\) are those vertices which are not adjacent to \(s\).

We recall that the binomial coefficients satisfy

\(\dbinom{m+n-2}{m-1} = \dbinom{m+n-3}{m-2} + \dbinom{m+n-3}{m-1} = \dbinom{m+n-3}{m-2} + \dbinom{m+n-3}{n-2}\)

So either \(|S_1| \geq \binom{m+n-3}{m-2}\) or \(|S_1| \geq \binom{m+n-3}{m-1}\). If the first option holds, and \(S_1\) does not have an independent set of size \(n\), then it contains a complete subgraph of size \(m−1\). It follows that we may add \(x\) to this set to obtain a complete subgraph of size \(m\) in \(G\).

Similarly, if the second option holds, and \(S_2\) does not contain a complete subgraph of size \(m\), then \(S_2\) contains an independent set of size \(n−1\), and we may add \(x\) to this set to obtain an independent set of size \(n\) in \(G\).