# Counterexample for $R(4,4) \neq 8$

I try to find a counterexample for $R(4,4)\neq 8$. (R is the Ramsey-number).

I drew a graph with 8 vedges and I coloured all edges $(v_i,v_j)$ with $i-j =\pm 2,4,6$ in the same colour (for example in red). But then I'll find a $K_4$ with $(v_1,v_3,v_5,v_7)$, which is definitely not a counterexample.

Perhaps someone can help me out here? Thanks in advance.

-
I added the ramsey-theory tag. The stronger result $R(4,3)>8$ is shown here: cut-the-knot.org/arithmetic/combinatorics/Ramsey43.shtml – Andrés E. Caicedo Jan 27 '13 at 22:12

## 2 Answers

A simple way to see that $R(4,4) > 9$ is to take three disconnected copies of $K_3$:s. Of course this is very far from being optimal, since the true value is $R(4,4)=18$.

-
Ah, of corse. Thank you very much. – ulead86 Jan 28 '13 at 5:47

Here's a proof that $R(4,4)>17$ which I "borrowed" from cut the knot. We take the $17$-vertex circulant graph with edges of distances $\{1,2,4,8\}$ as the red edges and distances $\{3,5,6,7\}$ as the blue edges.

So we have the red edges:

and the blue edges:

Since the graph is vertex transitive it is sufficient to check that the neighbourhood of some fixed vertex does not contain an induced monochromatic $K_3$.

We check the monochromatic neighbourhoods:

and

and find there are no triangles (ignoring the dotted edges).

-
nice :) thank you – ulead86 Apr 16 '13 at 14:10
Your answers are always expertly crafted. Did you make your pictures in TikZ, by any chance? I would like to "borrow" the code for a talk I'm putting together. – Austin Mohr Mar 9 '14 at 1:06