Ramsey Number proof: $R(3,3,3,3)\leq 4(R(3,3,3)-1) + 2$

$\begingroup$

I am trying to prove:

$R(3,3,3,3)\leq 4(R(3,3,3)-1) + 2$

I am confused as to how one can go from a $4$ color problem to a $3$ color problem by multiplying and adding.

edit: $R$ is the Ramsey number

$\endgroup$ 6

1 Answer

$\begingroup$

(Big hint/spoiler)

Consider a graph of order $4(R(3,3,3)−1)+2$ whose edges are coloured using four colours. Pick a vertex $x$, and for each $1\leq i\leq 4$ let $V_i$ denote the set of vertices whose edge to $x$ uses the $i$'th colour. By the pigeonhole principle, some $V_i$ has order at least $R(3,3,3)$. Now consider two cases:

• some edge in $V_i$ uses colour $i$
• no edge in $V_i$ uses colour $i$

$\endgroup$

Your Answer

Sign up or log in

Sign up using Google Sign up using Facebook Sign up using Email and Password Submit

Post as a guest

Post Your Answer Discard

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy