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.

Motivating example

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

In fact,  is the minimal party size that guarantees this property. Consider the following graph:There are  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  is not sufficient.

Ramsey's theorem and Ramsey numbers

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

Fix positive integers . Every sufficiently large party will contain a group of  mutual friends or a group of  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  is a graph on  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  in a graph is a copy of  inside the graph.

So Ramsey's theorem, restated, is: Fix positive integers . Every complete graph on sufficiently many vertices, with every edge colored blue or red, will contain a red clique of  vertices or a blue clique of  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  is the smallest party size that guarantees a group of  mutual friends or a group of  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  vertices or a blue clique of  vertices.

The theorem generalizes to an arbitrary (finite) number of colors; there is a Ramsey number  that guarantees a monochromatic clique of  vertices with color  on a sufficiently large graph.

 trivially. (There is no coloring requirement of a clique with 1 vertex.)

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

. This is a restatement of the example in the introduction.

Proof of Ramsey's theorem

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

So the proof gives an inequalityNote that this immediately shows . The proof of the theorem is in fact a generalization of the proof that .

Bounds on Ramsey numbers

The computation of  is a very difficult problem in general, even for small  and . The inequality for  looks a bit like Pascal's identity, and in fact an easy induction using Pascal's identity shows thatExact values of  for  are only known for . Current research shows only that , 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  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  given in the introduction).

 Brilliant.org.