Ramsey Theory

Ramsey theory is the study of questions of the following type: given a combinatorial structure (e.g. a graph or a subset of the integers), how large does the structure have to be to guarantee the existence of some substructure (e.g. subgraph, subset) with a given property? The theory has applications in the design of communications networks and other purely graph-theoretical contexts, as well as interesting problems in elementary number theory.

The most well-known example of Ramsey theory is furnished by Ramsey's theorem, which generalizes the following brainteaser.

Show that any party with at least $6$ people will contain a group of three mutual friends or a group of three mutual non-friends.

---

Solution: Call the people A, B, C, D, E, F. Either A has three friends or three non-friends. Without loss of generality, suppose that B,C,D are all friends with A. Then if any pair of them are friends with each other, that pair plus A forms a group of three mutual friends. If no two of them are friends, then they are a group of three mutual non-friends. $\square$

In fact, $N = 6$ is the minimal party size that guarantees this property. Consider the following graph: There are $5$ vertices, each of which represents a person. Friends are connected by red edges, and non-friends are connected by blue edges. A group of three mutual friends would be represented by a red triangle, and a group of three mutual non-friends would be represented by a blue triangle. But neither of these is present anywhere in the graph, so $N=5$ is not sufficient.

The genesis of Ramsey theory is in a theorem which generalizes the above example, due to the British mathematician Frank Ramsey.

Fix positive integers $m,n$. Every sufficiently large party will contain a group of $m$ mutual friends or a group of $n$ mutual non-friends.

It is convenient to restate this theorem in the language of graph theory, which will make it easier to generalize. This requires some definitions:

A complete graph $K_n$ is a graph on $n$ vertices where every pair of vertices is connected by an edge.

A clique inside a graph is a set of vertices which are pairwise connected to each other; in other words, a clique of size $n$ in a graph is a copy of $K_n$ inside the graph.

So Ramsey's theorem, restated, is: Fix positive integers $m,n$. Every complete graph on sufficiently many vertices, with every edge colored blue or red, will contain a red clique of $m$ vertices or a blue clique of $n$ vertices. (Here a "red clique" means that every edge connecting two vertices in the clique is red. The vertices are not colored; the edges are.)

The Ramsey number $R(m,n)$ is the smallest party size that guarantees a group of $m$ mutual friends or a group of $n$ mutual non-friends. Alternatively, it is the minimum number of vertices a complete graph must have so that if every edge is colored blue or red, there is a red clique of $m$ vertices or a blue clique of $n$ vertices.

The theorem generalizes to an arbitrary (finite) number of colors; there is a Ramsey number $R(n_1,n_2,\ldots,n_k)$ that guarantees a monochromatic clique of $n_k$ vertices with color $k$ on a sufficiently large graph.

$R(m,1) = R(1,m) = 1$ trivially. (There is no coloring requirement of a clique with 1 vertex.)

$R(m,2) = R(2,m) = m$. This is because in $K_m$, either all the edges are colored red, in which case there is a red clique on $m$ vertices; or there is a blue edge somewhere, in which case the two vertices it connects are a blue clique on $2$ vertices. In other words, either everyone at the party is friends with everyone else, or there are two people who are not friends.

$R(3,3) = 6$. This is a restatement of the example in the introduction.

The goal is to show that $R(m,n)$ exists. Induct on $m+n$. If $m$ or $n$ equals $1$, we are done. For the inductive hypothesis, we show that a complete graph on $R(m-1,n) + R(m,n-1)$ vertices satisfies the condition of the problem.
To see this, take a vertex from the graph. Consider the subsets $V_r$ and $V_b$ of vertices connected to this vertex by red and blue edges, respectively. Then $|V_r| + |V_b| = R(m-1,n)+R(m,n-1)-1$, so either $|V_r| \ge R(m-1,n)$ or $|V_b| \ge R(m,n-1)$. In the former case, $V_r$ contains either a blue clique on $n$ vertices, in which case we are done, or a red clique on $m-1$ vertices; but putting that clique together with the original vertex produces a red clique on $m$ vertices. The latter case is similar. So the proof is complete by induction. $\square$

So the proof gives an inequality $$R(m,n) \le R(m-1,n) + R(m,n-1).$$ Note that this immediately shows $R(3,3) \le R(3,2) + R(2,3) = 3+3 = 6$. The proof of the theorem is in fact a generalization of the proof that $R(3,3) = 6$.

The computation of $R(m,n)$ is a very difficult problem in general, even for small $m$ and $n$. The inequality for $R(m,n)$ looks a bit like Pascal's identity, and in fact an easy induction using Pascal's identity shows that $$R(m,n) \le \binom{m+n-2}{m-1}.$$ Exact values of $R(m,n)$ for $3 \le m \le n$ are only known for $(m,n) = (3,3),(3,4),\ldots,(3,9),(4,4),(4,5)$. Current research shows only that $43 \le R(5,5) \le 49$, for example.

Better upper bounds are hard to come by, since in the absence of an elegant logical argument they require an enumeration of all possible colorings of $K_n$ and a demonstration that every coloring gives a monochromatic clique of the right size. Lower bounds only require one specific coloring that does not admit such a clique (e.g. the one for $R(3,3) \ge 6$ given in the introduction).