Find an upper bound for the Ramsey number R44 In other words

Find an upper bound for the Ramsey number R(4,4). In other words, find a number n such that if you color edges of Kn red and blue, you will always find a K4 with all edges of the same color. (Try to make n as small as possible)

Solution

By symmetry, you just have to show that 0 is not in any monochromatic K4. 0 is adjacent to 1,2,4,8,9,13,15,16. Suppose 1 is involved. 1 is adjacent to 2,9,16. No two of these are adjacent,

so that rules out a red K4 involving 0 and 1. Now you have to do the same kind of analysis for 0and 2, etc. Eventually, you rule out all red K4s.

Then you get to work on the potential blue K4s. You can do the same kind of analysis, or you can notice that taking x to 3x takes all red edges to blue and all blue to red, so if there\'s no red K4, there\'s no blue one either.

While this is true, it is also easy to show that if there is a K4 then there must be a K4 that has both 0 and 1 in its vertex set. So you only need to show that there is no edge in the induced subgraph formed by 2,9,16 and you are done.