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.

$r(k) := R(\underbrace{3,3,...,3}_k)$

(I.e. $r(k)$ is the minimum integer $n > 0$ such that every coloring of edges of $K_n$ in $k$ colors is guaranteed to produce a monochromatic triangle.) Show that for $k \ge 2$

$$r(k) \le k\big(r(k−1)−1\big) + 2$$

Can anyone help with this? Any hints are welcome! Thanks

share|improve this question
2  
this is third problem in a very short amount of time that you have asked a question about the coloring of graphs. Is this homework? What work have you done on your own? –  Jebruho Nov 4 '12 at 22:45
2  
Also, if you are going to be a regular here, you're contributions will look much better if you learn how to format them properly. See, e.g., meta.math.stackexchange.com/questions/107/… and meta.math.stackexchange.com/questions/5020/… and meta.math.stackexchange.com/questions/1773/… –  Gerry Myerson Nov 4 '12 at 22:51
    
no, these are practice questions off the internet to study for a midterm. i've done some successfully, however i posted those which i wasn't able to do and looked topical to what's been covered in class. Ramsey theory is pretty much the one thing I'm having an insane amount of trouble with. i dont even know where to begin and there aren't enough corrected exercises online. –  Gogol Nov 4 '12 at 23:03
    
alright, i got this one as a recursion and got an inequality out of it. thanks anyway! –  Gogol Nov 5 '12 at 0:10
add comment

1 Answer

Assume we have a complete graph on $k(r(k-1)-1)+2$ vertices and $k$ edge colours [I am European]. Choose an arbitray vertex $v$. Divide the other $k(r(k-1)-1)+1$ vertices according to colour that connects them to $v$. At least one of these $k$ sets must have $r(k-1)$ vertices. The vertices in this set are all connected to $v$ by the same colour. That colour cannot be used between the vertices in that set (or else we find a triangle). So the set is internally coloured with $k-1$ colours, and must contain a monochromatic triangle.

This proof is very similar to the classic one that shows that $R(3,3,3) \le 17$, based on $R(3,3)=6$.

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.