Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
I added the ramsey-theory tag. The stronger result $R(4,3)>8$ is shown here: – Andrés E. Caicedo Jan 27 '13 at 22:12
up vote 3 down vote accepted

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$.

share|cite|improve this answer
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:

Red edges

and the blue edges:

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:

Red neighbourhood


Blue neighbourhood

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

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

Your Answer


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.