An upperbound for $R(3,p)$

Question

For $p\geq 3$, $R(3,p)\leq \frac{p^2+3}{2}$

I tried making use of the following result.

For $k,l\geq 2$, $R(k,l)\leq {{k+l-2} \choose {k-1}}$.

I got upper bound $\frac{p^2+p}{2}$.

Is there a result that should be used to get the aforementioned upper bound or should one proceed by construction ?

Answer 1

Use the bound: $$ R(k,l) \leq \begin{cases} R(k-1, l) + R(k, l-1) - 1 &\quad \text{if both $R(k-1, l)$ and $R(k, l-1)$ are even,} \\ R(k-1, l) + R(k, l-1) &\quad \text{otherwise.} \end{cases} $$ And do induction, conditioning on whether $p$ is even or odd.

One has: $$\begin{aligned} R(3,p) &\leq R(2,p) + R(3,p-1) \\ &\leq p + \frac{(p-1)^2 + 3}{2} \\ &\leq \frac{p^2 + 4}{2}.\end{aligned}$$ This is not what we want, but we can knock off half integers.

When $p$ is odd, we can knock a half integer off $\frac{p^2 + 4}{2}$.

When $p$ is even, $p-1$ is odd and is either $1$ or $3$ mod $4$, so $(p-1)^2 \equiv 1 \, (\text{mod } 4)$, and $\frac{(p-1)^2 + 3}{2} \in \mathbb{Z}$ is an even integer.

• If $R(3, p-1) < \frac{(p-1)^2 + 3}{2}$, then $R(3, p-1) \leq \frac{(p-1)^2 + 1}{2} $ and we're done.
• Otherwise, $R(3, p-1) = \frac{(p-1)^2 + 3}{2}$ and $R(3, p-1)$ and $R(2,p) = p$ is even, so

$$ R(3,p) \leq p + \frac{(p-1)^2 + 3}{2} - 1 < \frac{p^2 +3}{2}, $$ as desired.