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

.