Cotas de Ramsey por el método probabilístico

Los números de Ramsey: lo que sabemos y lo que no sabemos

El número de Ramsey $R(s,t)$ es el mínimo $n$ tal que toda 2-coloración de $K_n$ contiene un clique rojo de tamaño $s$ o un independiente azul de tamaño $t$. La existencia de $R(s,t)$ para todos $s,t$ fue demostrada por Ramsey en 1930.

Las cotas conocidas para $R(k,k)$ muestran una brecha exponencial:

$\sqrt{2}^k \lesssim R(k,k) \lesssim 4^k$.

La cota superior $R(k,k) \le \binom{2k-2}{k-1} \le 4^k$ sigue de la recurrencia $R(s,t) \le R(s-1,t) + R(s,t-1)$ y la fórmula binomial. La cota inferior $R(k,k) > 2^{k/2}$ es la prueba de Erdős de 1947 que presentamos en la Lección 3.1.

Mejorar cualquiera de estas dos cotas más allá del factor exponencial base sigue siendo uno de los problemas más famosos de la combinatoria. En 2023, Campos, Griffiths, Morris y Sahasrabudhe demostraron $R(k,k) \le (4-\varepsilon)^k$ para una constante $\varepsilon > 0$ pequeña, la primera mejora de la base exponencial de la cota superior en más de 75 años. La cota inferior de Erdős sigue sin mejorarse en el orden de magnitud.

La cota mejorada: el método de la alteración

Podemos mejorar la cota inferior de Erdős usando el método de la alteración (Erdős, Spencer, 1974). El argumento en la Lección 3.1 daba $R(k,k) > 2^{k/2}$ eligiendo $n = 2^{k/2}$ y mostrando que la esperanza del número de cliques monocromáticos de tamaño $k$ es $< 1$. La idea de la alteración es: incluso si la esperanza es $\ge 1$, podemos eliminar un vértice de cada clique monocromático y el grafo resultante sigue siendo grande.

Prueba por alteración. Tomamos $n = \lfloor k \cdot 2^{k/2} / (e\sqrt{2}) \rfloor$ y coloremos $K_n$ aleatoriamente. Sea $X$ el número de cliques monocromáticos de tamaño $k$. Por el cálculo de la Lección 3.1, $\mathbb{E}[X] = \binom{n}{k} \cdot 2^{1-\binom{k}{2}}$. Para $n = \Theta(k \cdot 2^{k/2})$, se tiene $\mathbb{E}[X] = \Theta(n)$ — la esperanza es del orden de $n$. Eliminamos un vértice de cada clique monocromático de tamaño $k$. El número de vértices eliminados es a lo sumo $X$, y el grafo resultante $G'$ tiene al menos $n - X$ vértices y no contiene cliques monocromáticos de tamaño $k$. Como $\mathbb{E}[n - X] = n - \mathbb{E}[X] = n - O(n) = \Omega(n)$, existe una coloración donde $n - X = \Omega(n)$. Con la elección correcta de la constante en $n$, el grafo $G'$ tiene $\Omega(k \cdot 2^{k/2})$ vértices, lo que da:

Cotas para $R(k,l)$ con $k$ fijo y $l \to \infty$

Para el caso asimétrico $R(k,l)$ con $k$ fijo y $l$ grande, el método probabilístico da una cota inferior precisa. Se puede demostrar:

$R(k,l) \ge c_k \cdot \left(\frac{l}{\log l}\right)^{(k-1)/2}$

para una constante $c_k > 0$ que depende solo de $k$. La prueba usa $G(n,p)$ con $p = c\cdot(l/\log l)^{-1/(k-1)}$: el número de cliques rojos de tamaño $k$ tiene esperanza pequeña (por elección de $p$), y el número de independientes azules de tamaño $l$ también. La alteración elimina vértices para destruir cliques y grandes independientes, dejando un grafo con muchos vértices.

Para $k=3$, esto da $R(3,l) \ge c(l/\log l)$ para alguna constante $c > 0$. El resultado asintótico exacto $R(3,l) = \Theta(l^2/\log l)$ fue una de las mayores hazañas de la combinatoria del siglo XX, demostrado por Kim en 1995 mediante el proceso de Rödl (un proceso aleatorio refinado).

La cota superior $R(3,l) \le O(l^2/\log l)$ sigue de argumentos de grafos de Ramsey-libres y el Teorema de Turán, como vimos en el Capítulo 2.

Grafos de Paley y la conexión con la teoría de números

Una de las preguntas más fascinantes de la combinatoria es si existe una construcción explícita de grafos de Ramsey —grafos con $n$ vértices sin clique ni independiente de tamaño $C \log n$ para alguna constante $C$. Si tal construcción existiera, probaría que los números de Ramsey tienen cota inferior casi lineal (en $\log n$), pero con una constante mejor que la probabilística.

Los grafos de Paley son el principal candidato. Dado un primo $q \equiv 1 \pmod{4}$, el grafo de Paley $P(q)$ tiene vértice por cada elemento de $\mathbb{F}_q$ y arista $\{a,b\}$ si $a-b$ es un residuo cuadrático en $\mathbb{F}_q$. Es bien sabido que $P(q)$ es strongly regular con parámetros $(q, (q-1)/2, (q-5)/4, (q-1)/4)$.

Se conjetura que $\alpha(P(q)) = O(\sqrt{q} \log q)$, lo que implicaría $R(k,k) \ge 2^{\Omega(k^2)}$ —una mejora exponencial enorme sobre la cota probabilística. Sumas de caracteres de Gauss permiten probar $\alpha(P(q)) \le 2\sqrt{q}$ (cota cuadrática), pero la cota conjectural $O(\sqrt{q} \log q)$ equivale a la Hipótesis de Riemann Generalizada para funciones $L$ sobre $\mathbb{F}_q$. Esta es una de las conexiones más inesperadas entre la combinatoria y la teoría analítica de números.

El método probabilístico en Ramsey generalizado: hipergrafos

Sea $R^{(r)}(k;c)$ el número de Ramsey de hipergrafos: el mínimo $n$ tal que toda $c$-coloración de los $r$-subconjuntos de $[n]$ contiene un conjunto monocromático de tamaño $k$. Para $r=2, c=2$ se tiene $R^{(2)}(k;2) = R(k,k)$. Para $r=3$ (tri-hipergrafos), el crecimiento es radicalmente diferente:

$\exp(c_1 \cdot 2^{k/2}) \le R^{(3)}(k;2) \le \exp(c_2 \cdot 2^k)$.

La cota inferior (torre exponencial simple) se demuestra por un argumento de "stepping up" de Erdős-Hajnal: se puede "empujar hacia arriba" la cota de $r=2$ a $r=3$ ganando un exponente. La prueba usa el método probabilístico con una coloración aleatoria de tri-aristas y un argumento de doble conteo.

Para $r$ general, los números de Ramsey crecen como torres exponenciales de altura $r-1$. Esta explosión fue una de las primeras indicaciones de que los problemas de Ramsey son computacionalmente incomprensibles: el número $R^{(3)}(5;2)$ ya es desconocido, aunque está acotado entre $\exp(\exp(c_1))$ y $\exp(\exp(c_2))$.

Síntesis: el método probabilístico como herramienta olímpica

Para los Selectivos IMO, el método probabilístico aparece en tres formas principales: (1) Coloraciones aleatorias: colorear vértices/aristas/enteros aleatoriamente y usar esperanza para probar existencia de coloraciones buenas. (2) Permutaciones aleatorias: elegir un orden aleatorio para probar existencia de recorridos, enumeraciones o funciones con propiedades especiales. (3) Subconjuntos aleatorios: elegir un subconjunto aleatorio (cada elemento con probabilidad $p$ independiente) y controlar sus propiedades.

Los cálculos siempre siguen el mismo patrón: (a) definir el espacio, (b) identificar indicadoras, (c) calcular esperanza por linealidad, (d) concluir existencia. El reto olímpico es (a): elegir el espacio de probabilidad correcto que hace el cálculo en (c) tratable y la conclusión en (d) útil.

El capítulo 3 cierra con esta visión: el método probabilístico es una forma de pensar sobre la combinatoria, no solo una técnica. Preguntar "¿qué pasa si elijo esto aleatoriamente?" es, en muchos problemas, la apertura más poderosa. Los problemas del Capítulo 3 que siguen están diseñados para que practiques reconocer este patrón desde el enunciado.