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\left(n_{1},\cdots ,n_{r_{2}},n_{r_{1}},n_{r}\right)\leq R\left(n_{1},\cdots ,n_{r_{2}},R\left(n_{r_{1}},n_{r}\right)\right)$

Hint: Let $n=R\left(n_{1},\cdots ,n_{r_{2}},R\left(n_{r_{1}},n_{r}\right)\right)$ and consider an edge colouring of $K_{n}$ with $r$ colours, say $c_{1},\cdots ,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\left(n_{1},\cdots ,n_{r_{2}},R\left(n_{r_{1}},n_{r}\right)\right)$ 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,\cdots ,r-2$ or a complete sub-graph of size $R\left(n_{r_{1}},n_{r}\right)$ in the color “blurred”. If we look at the definition of $R\left(n_{r_{1}},n_{r}\right)$, 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\left(n_{1},\cdots ,n_{r_{2}},R\left(n_{r_{1}},n_{r}\right)\right)$ has to be as least as big as the graph described by $R\left(n_{1},\cdots ,n_{r_{2}},n_{r_{1}},n_{r}\right)$.