1
$\begingroup$

$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

  • 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?2012-11-04
  • 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., http://meta.math.stackexchange.com/questions/107/faq-for-math-stackexchange/117#117 and http://meta.math.stackexchange.com/questions/5020/mathjax-basic-tutorial-and-quick-reference and http://meta.math.stackexchange.com/questions/1773/do-we-have-an-equation-editing-howto2012-11-04
  • 0
    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.2012-11-04
  • 0
    alright, i got this one as a recursion and got an inequality out of it. thanks anyway!2012-11-05

1 Answers 1