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).