1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ "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. $\endgroup$ – MateInTwo Jan 26 at 12:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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