# Ramsey number for paths

Let $n = R(P_{r+1}, c)$ be the smallest integer such that if $K_n$ is $c$-edge-coloured, then it contains a monochromatic subgraph isomorphic to $P_{r+1}$, the path of length $r$. I need to show that $R(P_{r+1}, c) \leq r^c + 1$.

I believe that the best known bound is linear in terms of $r$, so this is really rough, but I still can't get anywhere. I have tried modifying the usual proof of Ramsey's theorem, showing that $R(s, t) \leq R(s - 1, t) + R(s, t - 1)$ (Erdos-Szekeres), but to no avail. I have also tried proving the bound: $$R(P_{r+1}, c) - 1\leq r(R(P_{r+1}, c - 1) - 1)$$ by partitioning a complete graph into a product of $r$ complete subgraphs. I do know know if this bounds holds, but if it did, I would get the desired answer.

-

We proceed by induction on $c$.
When $c = 1$, $R(P_{r + 1}, 1) \leq r + 1$, since $K_{r + 1}$ contains all possible edges between $r + 1$ vertices, and a path of length $r$ is one such choice.
Let $n = R(P_{r+1}, c)$, $G = K_n$. Let $G$ be $(c - 1)$-edge-coloured, and extend this to a $c$-edge-colouring of $H = K_{n + \lfloor r/2 \rfloor}$, where the new complete subgraph $K_{\lfloor r/2 \rfloor}$ is $1$-edge-coloured for a previous colour used in $G$, and all of the edges linking $G$ to this subgraph are $1$-edge-coloured in a new colour. This is a graph with no monochromatic path of length $r$, so: $$R(P_{r+1}, c) \leq R(P_{r}, c - 1) + \lfloor r/2 \rfloor$$ So, by the induction hypothesis: $$R(P_{r+1}, c) \leq r^{c-1} + 1 + \lfloor r/2 \rfloor \leq r^c + 1$$ And this last inequality is true since: \begin{align*} &r^{c-1} + 1 + \lfloor r/2 \rfloor \leq r^c + 1 \\ \iff &\lfloor r/2 \rfloor \leq r^{c-1}(r - 1) \end{align*} If $r$ is even, then $r \geq 2$ and: $$\frac{1}{2} \leq r^{c - 2}(r - 1)$$ This last inequality might not hold if $c = 1$, but in that case: $$\frac{1}{2} \leq 1 - \frac{1}{r}$$ and since $r \geq 2$, this is true.
If $r$ is odd, then $r \geq 1$ and: $$\frac{r - 1}{2} \leq r^{c - 1}(r - 1) \iff \frac{1}{2} \leq r^{c - 1}$$ Q.E.D.