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,\dots,n\}\). In this chapter, when \(X\) is a set and \(k\) is a non-negative integer with \(k\le |X|\), we borrow from our in-line notation for binomial coefficients and let \(C(X,k)\)\(C(X,k)\)family of all \(k\)-element subsets of \(X\) denote the family of all \(k\)-element subsets of \(X\). So \(|C([n],k)|=C(n,k)\) whenever \(0\le k\le n\).

Recall that the 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]\longrightarrow[n]\) is any function, then there is a \(k\)-element subset \(H\subseteq [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 yesat 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.

Next, here is the statement that generalizes this result.

Condensed: the full section is in Keller & Trotter, Applied Combinatorics.