Un límite superior para el número de Ramsey de un gráfico

Question

Intento demostrar el siguiente resultado, dado como ejercicio en mi libro:

$r(K_m+\bar{K_n},K_p+\bar{K_q})\le\binom{m+p-1}{m}n+\binom{m+p-1}{p}q$ .

Aquí $r(G,H)$ denota el número de Ramsey para los gráficos $G$ y $H$ es decir, el menor número entero positivo $t$ , de manera que cualquier gráfico $F$ de orden $t$ o bien contiene $G$ o $\bar{F}$ (el complemento de $F$ ) contiene $H$ . La unión de gráficos $G+H$ se define como el gráfico obtenido al dibujar primero $G\cup H$ y luego rellenar todas las aristas posibles entre los vértices de $G$ y $H$ .

Se agradecerá cualquier ayuda. Gracias.

Answer 1

Queremos demostrar que $$r(K_m+\bar{K_n},K_p+\bar{K_q}) \le \dbinom{m+p-1}{m}n + \dbinom{m+p-1}{p}q.\tag*{(1)}$$ Cuando $n = q = 1$ , $(1)$ se convierte en $$r(K_{m+1},K_{p+1}) \le \dbinom{m+p-1}{m} + \dbinom{m+p-1}{p} = \dbinom{m+p}{m} \tag*{(2)}.$$ Este límite clásico se deriva de la conocida desigualdad $$r(K_{m+1},K_{p+1}) \le r(K_{m},K_{p+1}) + r(K_{m+1},K_{p}) \tag*{(3)}.$$ (La desigualdad $(2)$ se desprende de $(3)$ por inducción en $m + p$ . Para los casos base, observe que, por ejemplo $r(K_{2},K_{p+1}) = p + 1$ .)

El hecho de que la desigualdad deseada sea una generalización fácil de un resultado clásico da una fuerte pista sobre la mejor manera de abordar la prueba. Felizmente, $(1)$ sigue efectivamente la misma línea que la prueba estándar de $(2)$ .

Reclamación: Si $m$ , $p \geq 2$ y $n$ , $q \geq 0$ entonces $$r(K_m+\bar{K_n},K_p+\bar{K_q}) \leq r(K_{m-1}+\bar{K_n},K_p+\bar{K_q}) + r(K_m+\bar{K_n},K_{p-1}+\bar{K_q}).$$

Prueba: Establecer $N = r(K_{m-1}+\bar{K_n},K_p+\bar{K_q}) + r(K_m+\bar{K_n},K_{p-1}+\bar{K_q})$ y bicolor $E(K_N)$ arbitrariamente con los colores rojo y azul. Elija $x \in V(K_N)$ . Por la elección de $N$ es fácil ver que debe haber o bien $r(K_{m-1}+\bar{K_n},K_p+\bar{K_q})$ bordes rojos que inciden en $x$ o $r(K_m+\bar{K_n},K_{p-1}+\bar{K_q})$ bordes azules que inciden en $x$ . Sin pérdida de generalidad, supongamos que esto último se cumple. Sea $U$ denotan el conjunto de vértices $u$ tal que $ux$ es azul. Ahora consideremos las aristas entre los vértices de $U$ . Si estos contienen una copia roja de $K_m+\bar{K_n}$ entonces hemos terminado. Si no, entonces por hipótesis deben contener una copia azul de $K_{p-1}+\bar{K_q}$ . Sin embargo, todas las aristas de $x$ a $U$ son azules, así que $x$ y la copia de $K_{p-1}+\bar{K_q}$ forme una copia azul de $K_{p}+\bar{K_q}$ . $\square$

Ya casi hemos terminado. Por inducción en $m + p$ tenemos $$r(K_m+\bar{K_n},K_p+\bar{K_q}) \le \dbinom{m+p-2}{m-1}n + \dbinom{m+p-2}{p}q\\ + \dbinom{m+p-2}{m}n + \dbinom{m+p-2}{p-1}q,$$ y $$\dbinom{m+p-2}{m-1}n + \dbinom{m+p-2}{p}q + \dbinom{m+p-2}{m}n + \dbinom{m+p-2}{p-1}q = \dbinom{m+p-1}{m}n + \dbinom{m+p-1}{p}q.$$

Finalmente, para el caso base, se puede demostrar por el mismo método anterior que $r(K_1+\bar{K_n},K_1+\bar{K_q}) \le n + q$ . Esto completa la prueba.