Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

1 Answer 1

up vote 0 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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