Número de Ramsey para caminos

Question

Deje $n = R(P_{r+1}, c)$ ser el entero más pequeño tal que si $K_n$ $c$- borde de color, a continuación, contiene un monocromático subgrafo isomorfo a $P_{r+1}$, el camino de la longitud de la $r$. Necesito mostrar que $R(P_{r+1}, c) \leq r^c + 1$.

Yo creo que el mejor conocido obligado es lineal en términos de $r$, así que esto es realmente difícil, pero todavía no puedo llegar a ninguna parte. He intentado modificar la prueba usual de la del teorema de Ramsey, mostrando que $R(s, t) \leq R(s - 1, t) + R(s, t - 1)$ (Erdos-Szekeres), pero fue en vano. También he tratado de demostrar que el obligado: $$R(P_{r+1}, c) - 1\leq r(R(P_{r+1}, c - 1) - 1)$$ mediante la partición de un grafo completo en un producto de la $r$ completa subdiagramas. Hago saber saber si este tiene límites, pero si lo hiciera, me gustaría conseguir la respuesta deseada.

Por favor, ayudar con consejos, no soluciones completas. Gracias.

Answer 1

Procedemos por inducción sobre $c$.

Cuando $c = 1$, $R(P_{r + 1}, 1) \leq r + 1$, desde $K_{r + 1}$ contiene todos los posibles bordes entre las $r + 1$ vértices, y un camino de longitud $r$ es uno de esos elección.

Vamos $n = R(P_{r+1}, c)$, $G = K_n$. Deje $G$ $(c - 1)$- borde de color, y se extiende a un $c$-edge-la coloración de las $H = K_{n + \lfloor r/2 \rfloor}$, donde la nueva completa subgrafo $K_{\lfloor r/2 \rfloor}$ $1$- borde-de color de un color que se utiliza en $G$, y todos los bordes de la vinculación de $G$ a este subgrafo se $1$-borde de color en un nuevo color. Este es un gráfico sin monocromática camino de la longitud de la $r$, así: $$R(P_{r+1}, c) \leq R(P_{r}, c - 1) + \lfloor r/2 \rfloor$$ Entonces, por la hipótesis de inducción: $$R(P_{r+1}, c) \leq r^{c-1} + 1 + \lfloor r/2 \rfloor \leq r^c + 1$$ Y esta última desigualdad se cumple ya que: \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*} Si $r$ es incluso, a continuación, $r \geq 2$ y el: $$\frac{1}{2} \leq r^{c - 2}(r - 1)$$ Esta última desigualdad no podría mantener si $c = 1$, pero en caso de que: $$\frac{1}{2} \leq 1 - \frac{1}{r}$$ y desde $r \geq 2$, esto es cierto.

Si $r$ es impar, entonces $r \geq 1$ y el: $$\frac{r - 1}{2} \leq r^{c - 1}(r - 1) \iff \frac{1}{2} \leq r^{c - 1}$$ Q. E. D.