Ramsey Number R(4,4)

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?

Thanks.

-
You don't color $i$ and $j$ red (or blue), you color the edge joining them red (or blue). – Gerry Myerson May 7 '12 at 6:54
Yes, that was a typo. – Shahab May 7 '12 at 7:22
If you like pictures; see my answer here. – Douglas S. Stones Apr 17 '13 at 18:41

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*}

-
I don't know what $N(3,4;2)$ means; a fortiori, I don't know that it equals $9$, nor that $N(4,4;2)\le N(3,4;2)+N(4,3;2)$. – Gerry Myerson May 8 '12 at 4:18
My apologies for not clarifying. $N(m,n;k)$ is the generalized Ramsey's number $R(m,n)$, except for k colors. We use Ramsey's theorem for $k=2$ to show that $N(m,n;2)\leq N(m,n-1;2)+N(m-1,n;2)$ which is the upper bound for Ramsey numbers, in this case $18$, which is why showing that $N(4,4;2)\geq18$ would prove that $N(4,4;2)=18$. Generally, we cannot get such equalities, but rather only bounds for the Ramsey numbers. You can show that $N(3,4;2)=9$ using the same argument above except showing that for $K_8,\ \mathbb{Z}_{8},$ there are no red triangles or green $K_{4}$, relying on $N(3,3;2)=6$ – Han Altae-Tran May 9 '12 at 0:55
I think $N(m,n;k)$ does not meanr $k$ colors, I don't understand how to interpret that. Perhaps you mean 2 colors but instead of coloring a simple graph you are now coloring the hyperedges of a hypergraph where each k-subset of the N vertices forms a hyperedge. – Shahab May 9 '12 at 13:15
You are correct. We actually have $N(q_{1},\dots,q_{s},k)$, where $s$ is the number of colors, and $k$ the size of the colored subsets (I had mixed this up previously). This notation is taken from Lint and Wilson's A Course in Combinatorics if you want further reference. – Han Altae-Tran May 9 '12 at 19:08

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.

-