Given a natural number , write for the complete graph on vertices, and for the edgeless graph on vertices.
As explained in problem 47.10 from the textbook, given natural numbers , the notation
means that is so large that whenever is a graph on vertices, either contains a copy of as a subgraph, or a copy of as an induced subgraph.
We denote the negation of this statement by . In detail, this means that there is a graph on vertices such that for any collection of vertices of , at least one of the edges between them is not in , and also for any collection of vertices of , at least of the edges between them is in .
Note that if then also:
- for any , and
- for any .
Clearly, and for any . It is also clear that for any . When , however, the determination of the smallest such that is a subtle and difficult problem. This is called the Ramsey number of . We will denote it , so
and, if , then .
Proof: Consider a graph with . We need to show that either there is a copy of or of as an induced subgraph of .
Let . Divide the remaining vertices of into two sets and by setting
where means that there is an edge between and . We have and therefore either or . Otherwise, and , from which it follows that .
Suppose first that . Since , then the subgraph of induced by either contains a copy of or an induced copy of . In the latter case, is also an induced subgraph of , and we are done. In the former case, let be a subset of of size such that the subgraph of induced by is (isomorphic to) . Then, by definition of , the subgraph of induced by is isomorphic to , and we are done as well.
If, on the other hand, , the symmetric argument holds: Either there is a subset of of size whose induced subgraph is , and we are done, or else contains a copy of . But then (by definition of ) we have that is a copy of .
We have shown that in all cases either contains a copy of or of , as we needed to prove.
- Since and , it follows that . A pentagon is an example of a graph witnessing , and therefore .
- Since and , then . On the other hand, an octagon with two of its main diagonals is an example of a graph witnessing This means that is either 9 or 10. That it is actually 9 is a consequence of the following general result:
Proof: We argue as before: Let be a graph with vertices. Given , define and as before, and note that . There are three cases:
- . The result then follows by arguing as in the previous proof.
- . Again, the result follows as in the previous proof.
- and . Since , we must have that in fact and . Note that (by definition) , where is the degree (or valence) of .
If there is at least one for which we have either case 1 or 2, we are done. But this must actually happen. Otherwise,
is an odd number, since both and are even by assumption. However, as shown in Theorem 46.5 from the textbook, for any graph , we have that
which is obviously an even number. This contradiction completes the proof.
Theorems 1 and 2 provide us with an obvious algorithm to obtain upper bounds for the values of the Ramsey numbers , but these bounds are usually not optimal. For example,
so . However, the exact value of is 25.
For up-to-date bounds on the Ramsey numbers and references, the online survey Small Ramsey numbers by Stanislaw Radziszowski (The Electronic Journal of Combinatorics) is highly recommended. Typeset using LaTeX2WP. Here is a printable version of this post.