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.

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|improve this question
    
I added the ramsey-theory tag. The stronger result $R(4,3)>8$ is shown here: cut-the-knot.org/arithmetic/combinatorics/Ramsey43.shtml –  Andres Caicedo Jan 27 '13 at 22:12
add comment

2 Answers

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|improve this answer
    
Ah, of corse. Thank you very much. –  ulead86 Jan 28 '13 at 5:47
add comment

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

and

Blue neighbourhood

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

share|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 at 1:06
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.