9.3. Generalized Ramsey Numbers
Theorem 9.7. Let k and positive
integers
. If n is sufficiently large then every colour
of
with k
colours is such that for some
, it contains a
coloured
with the i-th colour.
Proof.
We will denote the
minimal n by .
We will proof by induction on the number of colours k.
The assertion is true
for .
Suppose that the
assertion holds for colours.
Now we colour the graph
with k
colours, and we replace the first two colours by a new one.
If n is large
enough then either there is a coloured
with the i-th colour for some
, or else there is a
coloured
with the new colour, that is coloured with the first two (original) colour.
- In the first case we are at home.
- In the second case for i=1 or i=2
we can find a
in
coloured with the i-th colour.
The Problem:
Let and
be
arbitrary graphs. Given n, is it true that every red-blue colouring of
the edges of
contains a
red
or a blue
?
Since is a
subgraph of
, where
, the answer is clearly "yes" if
.
Denote by the
smallest value of n that will ensure an affirmative answer. This value
called as generalized Ramsey number.
Some basic assertions:
-
.
-
.
We shall determine for some simple
pairs
.
Theorem 9.8. (Chvatal, 1977) : Let be a tree
of order s. Then
