Sign up ×
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 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.

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

1 Answer 1

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 cease 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 Aug. 22, 2011, in the Electronic Journal of Combinatorics. (I see I had suggested the same paper as an answer to this other question.)

share|cite|improve this answer

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.