Determining the graph Ramsey number $R(C_4,C_4)$

Question

What is the smallest $n$ such that every 2-coloring of the edges of $K_n$ contains a red or blue 4-cycle (not $K_4$)? I am given that $R(4,4) \le 18$ and $R(3,5) \le 14$.

Any help is greatly appreciated!

Answer 1

Well I think OP just meant $R(C_4,C_4)$ (the smallest $n$ so that any $2$-colouring of the edges of $K_n$ contains a monochromatic copy of $C_4$). Here's the idea of a solution.

In fact $R(C_4,C_4)=6$ and actually the proof has nothing to do with the values of $R(4,4)$ and $R(3,5)$, but one does need to know that $R(3,3)=6$.

So after finding a 2-colouring of $E(K_5)$ without a monochromatic $C_4$, one proceeds as follows. Suppose there is a $2$-colouring (red and blue) of $E(K_6)$ with no monochromatic $C_4$, and fix such a colouring. We know that there is a monochromatic triangle, say a red one on vertices $v_1,v_2,v_3$. Let $u_1,u_2,u_3$ be the other vertices.

First show that for any $u_i$, there is exactly one red edge to $\{v_1,v_2,v_3\}$. Next show that for any $v_i$, there is exactly one red edge to $\{u_1,u_2,u_3\}$. Conclude that there still must be a monochromatic $C_4$, a contradiction.