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
and
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.
For example:
- 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,
and
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.