Ramsey Number $R(4,4) = 18$

$\begingroup$

I wanted to know how to prove that $R(4,4)= 18$ without having to draw the graph.

I assume that I will have to start by proving that $R(4,4) \geq 17$. Can I also prove it by using $R(3,4) = 9$?

$\endgroup$

1 Answer

$\begingroup$

The recurrence $R(r,s) \leq R(r-1,s)+R(r,s-1)$ implies that $R(4,4) \leq 2R(3,4)=18$. So it suffices to prove $R(4,4)>17$ by exhibiting a graph on $17$ vertices that does not contain a $K_4$ and whose complementary graph does not contain a $K_4$.

This page exhibits such a graph (and the picture is not strictly necessary).

$\endgroup$ 1

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