Ramsey Number $R(4,4)$

Question

In trying to deduce the lower bound of the Ramsey number $R(4,4)$.

I am following my book's hint and considering the graph with vertex set $\mathbb{Z}_{17}$ in which $\{i,j\}$ is colored red if and only if $i-j\equiv\pm2^i,i=0,1,2,3$; the set of non-zero quadratic (mod 17) and blue otherwise. This graph shows that $R(4,4)\ge 18$. That's all fine but how am I expected to convince myself of this without drawing a $17$-vertex graph.

Is there some way to mathematically justify that such a graph will not contain a monochromatic $K_4$ without drawing this graph?

Answer 1

We know that $N(3,4;2)=9$. By symmetry, we have that $N(4,3;2)=9$. Thus we have the following: $ \lbrack N(4,4;2)\leq N(3,4;2)+N(4,3;2)=18 \rbrack $

Thus we create a counterexample, $K_{17}$ that does not contain any red $K_{4}$ or green $K_{4}$. To do this, we label the vertices $v_{1}=1,\dots,v_{17}=17$. Then we take all edges, $(v_{i},v_{j})$ with $i-j\equiv\pm1,2,4\text{or}8$ to be red. First off, it is easy to show that the only 3 node closed paths that can be formed are by the vertices $T_{1}=\{v_{i},v_{i+1},v_{i+2}\}$ or $T_{2}=\{v_{i},v_{i+4},v_{i+8}\}$, or $T_{3}=\{v_{i},v_{i+2},v_{i+4}\}$ (i.e. sequences $i_{1},i_{2},i_{3}$ whose elements differ by $1,2,4,\text{or}8$), or some $T$ containing permutations of these nodes. Thus in order to form $K_{4}$ from one of these triangles, we must be able to find a vertex $v_{i_{4}}$ such that $v_{i_{4}}$ is connected to each $v_{i_{1}},\dots,v_{i_{3}}$(i.e. each 3-shuffle of any of the 4 vertices: $(v_{i_{j_{1}}},\dots v_{i_{j_{3}}})$ should contain a triangle, and thus $v_{i_{4}}$ such form a triangle with each of the other $v_{i_{j}}$. However, looking at the available triangles, we find that this is impossible. E.g. for $T_{1}$, adding a $v_{\ell}$ would not produce a triangle between $\{v_{i},v_{i+1},v_{\ell}\}$ for $\ell=i+4$, $i-4$, $i+8$, $i-8$. The same holds for $T_{2}$, $T_{3}$ for similar reasons.

Now we look at the set of green edges (the edges $(v_{i},v_{j})$ with $i-j\equiv3,5,6,7$). (note that we do not include $9$ because in this situation, a difference of $8$ is equivalent to a difference of $9$ by symmetry of the graph. We can only have the following triangles $T_{1}=\{v_{i},v_{i+3},v_{i+6}\}$, $T_{2}=\{v_{i-5},v_{i},v_{i+7}\}$ since $-12\bmod17=5$, and $T_{3}=\{v_{i-5},v_{i},v_{i+6}\}$ for similar reasons. However, by the same reasoning above, we cannot form $K_{4}$ from these triangles using the available vertices and edges. E.g. For $T_{1}$, we cannot add $v_{i-5}$ (because $\{v_{i-5},v_{i},v_{i+3}\}$ is not an available triangle) or $v_{i+5}$ or $v_{i-7}$ or $v_{i+7}$ for similar reasons. Thus we see that we cannot form a red or green $K_{4}$ in this counter example, so we have shown that \begin{eqnarray*} N(4,4;2) & \nless & 18\implies\\ N(4,4;2) & = & 18 \end{eqnarray*}

Answer 2

By symmetry, you just have to show that $0$ is not in any monochromatic $K_4$. $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 $K_4$ involving $0$ and $1$. Now you have to do the same kind of analysis for $0$ and $2$, etc. Eventually, you rule out all red $K_4$s. Then you get to work on the potential blue $K_4$s. 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 $K_4$, there's no blue one either.

While this is true, it is also easy to show that if there is a $K_4$ then there must be a $K_4$ 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.