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.
Please help with hints, not complete solutions. Thank you.
 A: 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.
