Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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
add comment

2 Answers

up vote 1 down vote accepted

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

share|improve this answer
    
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
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.