# Bounds on Ramsey Numbers

I'm working on a script with a section on Ramsey Theory. I know that $$R(s,t) \leq R(s-1,t) + R(s,t-1)$$ and that you can add a -1 on the right side if both $$R(s-1,t)$$ and $$R(s,t-1)$$ are even. Using this inductively, one can prove $$R(s,t) \leq {s + t - 2 \choose s-1}$$, or $$R(3,t) \leq \frac{1}{2} \cdot (t^2 + t)$$. Now, my script claims that this can be sharpened using the two upper inequalities to $$R(3,t) \leq \frac{1}{2} \cdot (t^2 + 3)$$. How? I've been trying this for the past half hour and I can't find an answer. Thanks in advance for any help.

Observe first that $$R(2,t) = t$$ since any $$2$$-coloring of $$K_t$$ either contains an edge of the first color, or else is a monochromatic $$K_t$$ of the second color.

This, together with your recurrence for $$R(s,t)$$, gives: $$R(3,t) \le \begin{cases} R(3,t-1) + t - 1 & \text{if R(3,t-1) and t are both even,} \\ R(3,t-1) + t & \text{otherwise.} \end{cases}$$ (Okay, technically the first case applies if our upper bound on $$R(3,t-1)$$ is even, as well as $$t$$; it doesn't matter if the true value of $$R(3,t-1)$$ is odd.)

Try this for small values. We have

• $$R(3,3) = 6$$ as the base case.
• $$R(3,4) \le 6 + 4 - 1 = 9$$ since $$6$$ and $$4$$ are both even.
• $$R(3,5) \le 9 + 5 = 14$$.
• $$R(3,6) \le 14 + 6 - 1 = 19$$ since $$14$$ and $$6$$ are both even.

And so on. It becomes clear that our upper bound on $$R(3,t)$$ will be odd for even $$t$$ and even for odd $$t$$, so that we subtract $$-1$$ every other step. This may be shown by induction.

We subtract $$1$$ once for $$t=5$$, twice for $$t=7$$, three times for $$t=9$$, and so on, saving us a total of $$\frac{t-3}{2}$$ for odd $$t$$. (For even $$t$$ it is $$\frac{t-2}{2}$$, which is slightly better.) So the usual bound of $$R(3,t) \le \frac{t^2+t}{2}$$ improves to $$R(3,t) \le \frac{t^2+t}{2} - \frac{t-3}{2} = \frac{t^2+3}{2}.$$

• "Okay, technically the first case applies if our upper bound on R(3,t−1) is even, as well as t; it doesn't matter if the true value of R(3,t−1) is odd." That's what I hadn't understood. Thank you. – MateInTwo Jan 26 at 12:48