Bounds on Ramsey Numbers

Question

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.

Answer 1

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}.$