TU Wien:Diskrete Mathematik für Informatik UE (Gittenberger)/Übungen WS13/Beispiel 40

Show the following inequality for Ramsey numbers: If

r \geq 3

then

$R (n_{1}, \dots, n_{r_{2}}, n_{r_{1}}, n_{r}) \leq R (n_{1}, \dots, n_{r_{2}}, R (n_{r_{1}}, n_{r}))$

Hint: Let

n = R (n_{1}, \dots, n_{r_{2}}, R (n_{r_{1}}, n_{r}))

and consider an edge colouring of

K_{n}

with

r

colours, say

c_{1}, \dots, c_{r}

. Identify the colours

c_{r_{1}}

and

c_{r}

and apply the Ramsey property for

r_{1}

colours.

Solution

The following solution is largely based on the paragraph “Proof for More than Two Colors” from the website “ProofWiki”.

Lets assume we have an complete graph with $n = R (n_{1}, \dots, n_{r_{2}}, R (n_{r_{1}}, n_{r}))$ vertices. Colour the edges of this graph with $r$ colours. Then let us assume we can not see the difference between colour $r$ and colour $r - 1$ and lets call this colour that we are not able to differentiate âblurredâ. This leaves us with a $r - 1$ graph colouring.

This complete graph then either contains a complete sub-graph of colour $i$ of size $n_{i}$ for some $i = 1, \dots, r - 2$ or a complete sub-graph of size $R (n_{r_{1}}, n_{r})$ in the color âblurredâ. If we look at the definition of $R (n_{r_{1}}, n_{r})$ , we see that this sub-graph has to contain a sub-graph with either colour $r_{1}$ of size $n_{r_{1}}$ or a sub-graph of colour $r$ of size $n_{r}$ . This shows us that the complete graph described by $R (n_{1}, \dots, n_{r_{2}}, R (n_{r_{1}}, n_{r}))$ has to be as least as big as the graph described by $R (n_{1}, \dots, n_{r_{2}}, n_{r_{1}}, n_{r})$ .

TU Wien:Diskrete Mathematik für Informatik UE (Gittenberger)/Übungen WS13/Beispiel 40

Solution

Navigationsmenü

Suche