Cotas superiores e inferiores para números de Ramsey

La cota superior binomial: inducción y triángulo de Pascal

Hemos demostrado la recurrencia $R(s,t) \le R(s-1,t) + R(s,t-1)$. Con las condiciones iniciales $R(1,t) = 1$ y $R(s,1) = 1$ para todo $s,t \ge 1$ (un vértice solo siempre contiene trivialmente el clique de tamaño 1), y $R(2,t) = t$, $R(s,2) = s$ (para $t$ vértices existe un monocromático de tamaño 2 si hay al menos 2 de cualquier color), podemos resolver la recurrencia.

La recurrencia $R(s,t) \le R(s-1,t) + R(s,t-1)$ es idéntica en estructura a la identidad del triángulo de Pascal $\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$. Esta no es una coincidencia estilística: el triángulo de Pascal es precisamente la solución de la recurrencia con condiciones de frontera análogas. Llevando la analogía hasta su conclusión, se obtiene la cota superior fundamental.

Demostración por inducción sobre $s+t$: para $s=2$ o $t=2$, $R(2,t) = t = \binom{t}{1}$ y $R(s,2) = s = \binom{s}{s-1}$, que concuerdan con $\binom{s+t-2}{s-1}$. Para $s,t \ge 3$, asumiendo la cota para pares con suma menor, $R(s,t) \le R(s-1,t) + R(s,t-1) \le \binom{s+t-3}{s-2} + \binom{s+t-3}{s-1} = \binom{s+t-2}{s-1}$, donde la última igualdad es exactamente Pascal.

Esta cota tiene consecuencias inmediatas. Para $s = t = k$: $R(k,k) \le \binom{2k-2}{k-1} \sim \frac{4^{k-1}}{\sqrt{\pi(k-1)}}$. Así $R(k,k) \le 4^k$ (con constante implícita). La cota diagonal crece exponencialmente en $k$ con base $4$.

Numéricamente: $R(3,3) \le \binom{4}{2} = 6$ (exacto), $R(4,4) \le \binom{6}{3} = 20$ (el exacto es 18), $R(5,5) \le \binom{8}{4} = 70$ (el exacto es desconocido, entre 43 y 48), $R(6,6) \le \binom{10}{5} = 252$ (el exacto es desconocido, entre 102 y 165). La cota binomial se deteriora a medida que $k$ crece.

La cota inferior de Erdős: el argumento probabilístico

En 1947, Paul Erdős publicó una prueba de que $R(k,k) > 2^{k/2}$ usando un argumento de probabilidad. Esta fue la primera aplicación del método probabilístico en combinatoria, y marcó el nacimiento de toda una metodología. La idea es radicalmente simple: si coloreamos las aristas de $K_n$ de forma aleatoria uniforme (cada arista roja o azul con probabilidad $1/2$ independientemente), ¿cuál es la probabilidad de que ningún $k$-clique sea monocromático?

Para un conjunto fijo $S$ de $k$ vértices, la probabilidad de que $K_S$ (las $\binom{k}{2}$ aristas entre ellos) sea completamente rojo es $2^{-\binom{k}{2}}$. Por simetría, la probabilidad de que $K_S$ sea monocromático (rojo o azul) es $2 \cdot 2^{-\binom{k}{2}} = 2^{1-\binom{k}{2}}$. Sea $A_S$ el evento "$K_S$ es monocromático". Hay $\binom{n}{k}$ subconjuntos $S$ de $k$ vértices.

Por la unión de eventos (union bound): $\Pr[\text{existe }K_k\text{ monocromático}] \le \sum_S \Pr[A_S] = \binom{n}{k} \cdot 2^{1-\binom{k}{2}}$. Si esta suma es estrictamente menor que 1, entonces existe una coloración sin $K_k$ monocromático, lo que implica $R(k,k) > n$.

Estimamos con $\binom{n}{k} \le n^k / k!$ y buscamos $n$ tal que $\frac{n^k}{k!} \cdot 2^{1-\binom{k}{2}} < 1$. Esto se satisface cuando $n^k < k! \cdot 2^{\binom{k}{2}-1} \approx 2^{\binom{k}{2}}$ (ignorando el factorial, que es polinomial comparado con la exponencial), es decir $n < 2^{\binom{k}{2}/k} = 2^{(k-1)/2}$. Tomando $n = \lfloor 2^{k/2} \rfloor$ y verificando cuidadosamente la aritmética, se obtiene $R(k,k) > 2^{k/2}$.

El mensaje filosófico es más impactante que la cota misma: existencia sin construcción. No sabemos cómo es la coloración que evita el $K_k$ monocromático —el argumento simplemente dice que la mayoría de las coloraciones aleatorias la tienen. Esta tensión entre existencia no constructiva y construcción explícita es uno de los temas más ricos de la combinatoria contemporánea.

La brecha insalvada: entre $2^{k/2}$ y $4^k$

Durante más de 75 años, la cota inferior de Erdős $R(k,k) > (1+o(1))\frac{k}{e\sqrt{2}} \cdot 2^{k/2}$ y la cota superior $R(k,k) \le \binom{2k-2}{k-1} \sim \frac{4^k}{\sqrt{\pi k}}$ han permanecido como las mejores conocidas para el comportamiento diagonal. La base del exponente difiere: $\sqrt{2} \approx 1.41$ vs $4$. Reducir la cota superior a $c^k$ con $c < 4$, o mejorar la inferior más allá de $2^{k/2}$, son problemas abiertos de primer orden.

En 2023, Campos, Griffiths, Morris y Sahasrabudhe lograron el primer avance desde Erdős: demostraron $R(k,k) \le (4-\varepsilon)^k$ para alguna constante pequeña $\varepsilon > 0$. Esto no cambia la brecha exponencial fundamentalmente, pero es el primer movimiento en la cota superior en décadas. La técnica utiliza el "método de contenedores" y análisis de grafos aleatorios, herramientas que van mucho más allá de lo olímpico pero cuya existencia refleja la profundidad del problema.

Para cotas no diagonales $R(3,t)$: la situación es mejor comprendida. Se sabe que $R(3,t) = \Theta(t^2 / \log t)$. La cota superior $R(3,t) \le O(t^2/\log t)$ fue demostrada por Ajtai, Komlós y Szemerédi (1980), y la inferior por Kim (1995) usando el método probabilístico aleatorizado. Esto contrasta con la ignorancia en el caso diagonal.

Tabla de valores exactos conocidos de $R(s,t)$ con $s \le t$: $R(3,3)=6$, $R(3,4)=9$, $R(3,5)=14$, $R(3,6)=18$, $R(3,7)=23$, $R(3,8)=28$, $R(3,9)=36$, $R(4,4)=18$, $R(4,5)=25$. Todo lo demás es incompleto o desconocido. El número $R(5,5)$ se sabe que está entre 43 y 48. Nótese que la determinación de estos valores ha requerido décadas de cómputo intensivo y argumentos combinatorios ad hoc para cada caso.

La Conjetura de Erdős sobre $R(k,k)$: se cree que $R(k,k)^{1/k} \to L$ para alguna constante $L \in [\sqrt{2}, 4]$, y que $L = \sqrt{2}$ (es decir, la cota inferior es la verdad). Pero no existe evidencia rigurosa que descarte $L = 4$. Esta es una de las conjeturas más simples de enunciar y más difíciles de resolver en matemáticas discretas.

Refinamientos: el segundo momento y la alteración probabilística

El argumento de Erdős usa el primer momento (esperanza) y la cota de la unión. Refinamientos más poderosos usan el segundo momento o técnicas de alteración. La idea de alteración de Erdős y Selfridge es la siguiente: primero construye aleatoriamente una estructura grande, luego "repara" los defectos con un proceso determinístico o aleatorio adicional, obteniendo una estructura ligeramente más pequeña pero libre de defectos.

Para números de Ramsey, la alteración funciona así: genera la coloración aleatoria de $K_n$. Sea $X$ el número de $k$-cliques monocromáticos. $\mathbb{E}[X] = \binom{n}{k} \cdot 2^{1-\binom{k}{2}}$. Si $\mathbb{E}[X] < n/2$, entonces en la coloración resultante hay menos de $n/2$ cliques monocromáticos en promedio. Ahora borramos un vértice de cada $k$-clique monocromático: borramos a lo sumo $\mathbb{E}[X] < n/2$ vértices, quedando un grafo inducido sobre más de $n/2$ vértices sin $k$-clique monocromático. Esto implica $R(k,k) > n/2$, dando la misma cota que antes pero el argumento es más robusto.

El método del segundo momento, por su parte, usa $\text{Var}[X] = \mathbb{E}[X^2] - (\mathbb{E}[X])^2$ junto con la desigualdad de Chebyshev para mostrar que $X > 0$ con probabilidad positiva —o incluso que $X$ está concentrado alrededor de su media. Esto es relevante para demostrar cotas inferiores más precisas, aunque en el contexto de Ramsey la cota de Erdős se mantiene como la estándar.

Aplicación a problemas olímpicos: aunque el método probabilístico rara vez aparece explícitamente en olimpiadas nacionales, su esqueleto —contar el número esperado de "malos" eventos y concluir que no todos pueden ocurrir simultáneamente— sí aparece disfrazado. El "lema de Lovász local" (que veremos en el Capítulo 3) es el refinamiento más poderoso para situaciones donde los eventos malos son "casi independientes", y tiene aplicaciones directas en problemas de coloración de hipergrafos que aparecen en el IMO Shortlist.

Cotas para Ramsey multicolor: el caso de tres colores

Para tres colores, la recurrencia se generaliza: $R(s_1, s_2, s_3) \le R(s_1, R(s_2, s_3))$. Esto reduce el problema tricolor a una sucesión de problemas bicolores. Como $R(3,3) = 6$, la cota $R(3,3,3) \le R(3, R(3,3)) = R(3,6) = 18$ da exactamente el valor correcto: $R(3,3,3) = 17$.

Para el caso diagonal tricolor: $R(k,k,k) \le R(k, R(k,k)) \le R(k, 4^k)$. Ahora $R(k, m)$ para $m$ grande satisface $R(k,m) \le \binom{k+m-2}{k-1} \le m^{k-1}$. Sustituyendo, $R(k,k,k) \le (4^k)^{k-1} = 4^{k(k-1)}$, una cota doblemente exponencial. La cota inferior análoga por el método probabilístico tricolor da $R(k,k,k) > 3^{k/2}/\sqrt{k}$ (ejercicio con la misma idea de Erdős aplicada a 3-coloraciones). La brecha es ahora entre $3^{k/2}$ y $4^{k^2}$, mucho mayor que en el caso bicolor.

Una cota superior más ajustada para $r$ colores en la diagonal: $R_r(k) := R(k,\ldots,k) \le r^{r\binom{k}{2}}$ (cota trivial por reducción sucesiva). La cota inferior probabilística da $R_r(k) \ge r^{k/2 - 1}$. La diferencia cualitativa entre $r^{k/2}$ y $r^{k^2}$ muestra que los números de Ramsey multicolor son exponencialmente más difíciles de acotar que los bicolores.

Para concursos: la cota $R(3,3,3) = 17$ es frecuentemente utilizada en problemas que piden demostrar que en cierto conjunto de 17 objetos con tres tipos de relaciones, siempre aparece un triángulo "puro". La demostración del teorema de que $R(3,3,3) \le 17$ (que vimos en la Lección 1.1) junto con la cota inferior (coloración de $K_{16}$ sin triángulo monocromático en tres colores, construida a partir del plano proyectivo de Fano o directamente) constituyen un argumento completo nivel IMO/Shortlist.

Coda histórica: Paul Erdős era famoso por ofrecer premios en metálico por solucionar sus problemas abiertos. Por demostrar que $R(k,k)^{1/k}$ converge a un límite, ofrecía \undefined500. Por demostrar o refutar que $R(k,k) \le (2-\varepsilon)^k$ para algún $\varepsilon > 0$ fijo, \$100. Estos premios siguen vigentes en el sentido de que los herederos matemáticos de Erdős los mantienen vivos, aunque Erdős falleció en 1996.

Problemas olímpicos sobre cotas de Ramsey

IMO Shortlist 1992 C4 (variante): Demuestra que para todo entero $k \ge 2$, $R(k,k) \ge k \cdot 2^{(k-2)/2}$. Este es esencialmente el argumento de Erdős en versión más elemental, sin probabilidad explícita pero con un conteo de coloraciones cuidadoso. La idea: el número total de 2-coloraciones de $K_n$ es $2^{\binom{n}{2}}$. El número de coloraciones que tienen al menos un $k$-clique monocromático es a lo sumo $\binom{n}{k} \cdot 2 \cdot 2^{\binom{n}{2}-\binom{k}{2}}$ (fijamos el clique, coloreamos el resto libremente). Si este número es menor que $2^{\binom{n}{2}}$, existe una coloración sin clique monocromático.

Simplificando la condición: $\binom{n}{k} \cdot 2^{1-\binom{k}{2}} < 1$, que es exactamente la condición de Erdős. El alumno que sabe plantear este conteo puede resolver el problema sin conocer el método probabilístico formal. La habilidad clave es el doble conteo: contar "pares (coloración, clique monocromático)" de dos formas.

Para la cota superior, el argumento más limpio en competencias es el de paloma inductivo que ya conocemos. Pero hay una versión alternativa por conteo de subgrafos: si $G$ es un grafo de $n$ vértices y el número de aristas $e(G) > \binom{s+t-3}{s-1} \cdot (n/2)$, entonces $G$ contiene $K_s$ o el complemento contiene $K_t$. Esta formulación de densidad es más útil cuando el grafo tiene estructura adicional (bipartito, regular, etc.).

Aplicación directa en olimpiadas: "Sea $n$ personas en una fiesta donde cada una conoce exactamente a $k$ de las otras. Encuentra el menor $n$ para el cual necesariamente hay tres personas que se conocen mutuamente o tres que son mutuamente desconocidas." Esto pregunta por $R(3,3)$ en grafos $k$-regulares. Como el grafo $C_5$ es $2$-regular y evita $K_3$ monocromático en cualquier 2-coloración que no sea bipartita... espera, $C_5$ no es una 2-coloración de $K_5$. El problema se reformula correctamente como: grafo $G$ con $n$ vértices tal que $G$ contiene $K_3$ o $\overline{G}$ contiene $K_3$. Para $k$-regulares, la respuesta involucra el número de Ramsey y la densidad del grafo.