I am trying to prove that

$$R(s, t) ≤ R(s, t-1) + R(s-1, t) $$ for $s,t>2$, where $R(s,t)$ is the Ramsey number of $(s,t)$, and I'd be really grateful for a hint that gets me started.

  • Hint: pick a vertex $v$ in the graph, and split the other vertices in the graph into two sets: those connected to $v$ by red edges and those connected to $v$ by blue edges. – David Moews Jan 24 '12 at 0:17
up vote 4 down vote accepted

The usual approach is very nice: Suppose you are given the complete graph on $n=R(s,t-1)+R(s-1,t)$ vertices, and a coloring of its edges with colors red and blue.

Pick one of the vertices, call it $v$. Divide the remaining $n-1$ into two sets $A$ and $B$, according to whether they are joined to $v$ by a red or a blue edge, respectively. Let $a=|A|$ and $b=|B|$. Then $a+b=n-1$, so either $a\ge R(s,t-1)$ or $b\ge R(s-1,t)$. This is because otherwise, $a+b\le n-2$.

It should be easy to see how to continue from here.


Just for fun, let's compute some upper bounds using this inequality, knowing that $R(2,t)=R(t,2)=t$.

We have $R(3,3)\le R(2,3)+R(3,2)=3+3=6$. In fact, we have equality in this case. Moreover, the usual "party argument" one sees sometimes showing $R(3,3)\le 6$ is precisely the argument above.

$R(4,3)\le R(3,3)+R(4,2)=6+4=10$. In fact, one can extend the argument above a bit to show that if both $R(s,t-1)$ and $R(s-1,t)$ are even, then we have strict inequality. This means that $R(4,3)\le 9$, and again this is sharp.

$R(4,4)\le R(3,4)+R(4,3)=18$. Again, equality holds.

$R(5,3)\le R(5,2)+R(4,3)=5+9=14$ and, again, equality holds.

$R(5,4)\le R(5,3)+R(4,4)=14+18=32$. (So $R(5,4)\le31$ as both $14$ and $18$ are even.) In fact, $R(5,4)=24$, and the bound ceases being optimal around here.

Improving this bound turns out to be remarkably difficult and the subject of much work.

For a nice up to date list of the known values and bounds for Ramsey numbers, together with references, see the dynamic survey on "Small Ramsey numbers" by Stanisław Radziszowski, last updated March 3, 2017, in the Electronic Journal of Combinatorics. (I see I had suggested the same paper as an answer to this other question.)

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.