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 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.
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.
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 inequality Note that this immediately shows . The proof of the theorem is in fact a generalization of the proof that .
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 that Exact 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).