Teorema de Ramsey: el orden emerge del caos

El problema de la fiesta: orden inevitable en el caos

Imagina una fiesta con seis personas. Cada par de personas es o bien conocido o bien desconocido. Afirmamos que inevitablemente existe un grupo de tres personas que se conocen todas entre sí, o bien un grupo de tres personas que son todas mutuas desconocidas.

No importa cómo se distribuyan las amistades. No importa si la fiesta es un reencuentro de viejos amigos o una reunión de extraños. En cualquier configuración posible, ese grupo de tres existe. Esta es la esencia del Teorema de Ramsey: en estructuras suficientemente grandes, el orden es inevitable.

El número mágico seis tiene nombre propio: $R(3,3) = 6$. El hecho de que cinco personas sí pueden evitarlo —lo veremos con una construcción explícita— hace que el salto de cinco a seis sea una de las fronteras más sorprendentes de la combinatoria.

Este resultado, publicado por Frank Ramsey en 1930 en su artículo "On a Problem of Formal Logic", es el punto de partida de una rama entera de las matemáticas. Para la olimpiada, es una herramienta de primer nivel: reconocer su sombra en un problema puede ser la clave para una solución elegante.

Definición formal y la cota superior de Ramsey

Dados enteros positivos $s$ y $t$ con $s, t \ge 2$, el número de Ramsey $R(s,t)$ se define como el menor entero positivo $n$ tal que toda 2-coloración de las aristas del grafo completo $K_n$ (usando colores rojo y azul) contiene un $K_s$ completamente rojo o un $K_t$ completamente azul.

Equivalentemente, $R(s,t)$ es el menor $n$ tal que en todo grafo $G$ de $n$ vértices, o bien $G$ contiene a $K_s$ como subgrafo, o bien el complemento $\overline{G}$ contiene a $K_t$.

El resultado fundamental que hace finitos a todos los números de Ramsey es la siguiente cota superior por recurrencia. La demostración usa el principio de paloma de manera elegante.

Sea $v$ un vértice fijo de $K_n$. Los restantes $n-1$ vértices se dividen en dos grupos: $A$, los conectados a $v$ con arista roja, y $B$, los conectados con arista azul. Por el principio de paloma, si $n-1 \ge R(s-1,t) + R(s,t-1)$, entonces $|A| \ge R(s-1,t)$ o $|B| \ge R(s,t-1)$.

Si $|A| \ge R(s-1,t)$: por definición de $R(s-1,t)$, el subgrafo inducido por $A$ contiene un $K_{s-1}$ rojo o un $K_t$ azul. Si hay $K_t$ azul en $A$, terminamos. Si hay $K_{s-1}$ rojo en $A$, como todas las aristas de $A$ a $v$ son rojas, el $K_{s-1}$ más $v$ forma un $K_s$ rojo. El caso $|B| \ge R(s,t-1)$ es simétrico.

Demostración de $R(3,3) = 6$: cota superior e inferior

**Cota superior $R(3,3) \le 6$:** Utilizamos $R(2,3) = 3$ y $R(3,2) = 3$ (ejercicio: $R(2,t) = t$ para todo $t$). La recurrencia da $R(3,3) \le R(2,3) + R(3,2) = 3+3 = 6$.

Para la argumentación directa: sea $v$ un vértice de $K_6$. Tiene 5 vecinos. Por paloma, al menos $\lceil 5/2 \rceil = 3$ aristas hacia $v$ tienen el mismo color; digamos que $v$ está conectado en rojo con $a$, $b$, $c$. Si alguna arista entre $\{a,b,c\}$ es roja (digamos $ab$), entonces $\{v, a, b\}$ forman un $K_3$ rojo. Si ninguna arista entre $\{a,b,c\}$ es roja, entonces $\{a,b,c\}$ forman un $K_3$ azul. En cualquier caso, existe el triángulo monocromático.

**Cota inferior $R(3,3) > 5$:** Debemos exhibir una 2-coloración de $K_5$ sin triángulo monocromático. Considera los vértices $1, 2, 3, 4, 5$ en un pentágono regular. Colorea de rojo las aristas del pentágono (las "diagonales cortas" $12, 23, 34, 45, 51$) y de azul las diagonales largas ($13, 14, 24, 25, 35$). Verifica: ningún triángulo formado por tres vértices del pentágono tiene las tres aristas del mismo color. (Por simetría basta verificar un triángulo rojo y un azul posible.) Esta coloración del $C_5$ —llamada el grafo de Ramsey $C_5$— confirma que $K_5$ no fuerza el triángulo monocromático.

Conclusión: $R(3,3) = 6$.

El Teorema de Ramsey finito y la torre de doses

El argumento de recurrencia se generaliza sin dificultad al caso de $r$ colores.

Teorema de Ramsey (versión finita). Para cualquier entero $r \ge 1$ y cualesquiera enteros $s_1, s_2, \ldots, s_r \ge 2$, el número de Ramsey $R(s_1, s_2, \ldots, s_r)$ es finito.

**Prueba por inducción sobre $r$.** Para $r = 1$ es trivial. Para $r = 2$ es la recurrencia anterior. Para $r \ge 3$: en una $r$-coloración de $K_n$, fusionamos los colores $r-1$ y $r$ en un nuevo color "mixto". Esto reduce el problema a una $(r-1)$-coloración, donde el color mixto debe evitar un $K_{R(s_{r-1}, s_r)}$. Por hipótesis inductiva, si $n$ es grande, aparece un $K_{s_i}$ monocromático en algún color $i \le r-2$, o un $K_m$ en el color mixto (con $m = R(s_{r-1}, s_r)$). En el segundo caso, aplicamos el teorema para $r=2$ dentro de ese clique.

La cota que resulta de iterar la recurrencia $R(s,t) \le \binom{s+t-2}{s-1}$ implica que $R(k,k) \le \binom{2k-2}{k-1} \approx 4^k / \sqrt{k}$. La cota inferior de Erdős por el método probabilístico da $R(k,k) \ge (1+o(1)) \cdot k \cdot 2^{k/2} / e\sqrt{2}$. La brecha entre $2^{k/2}$ y $4^k$ ha resistido setenta años de esfuerzos: los números de Ramsey son notoriamente difíciles de calcular. Solo se conocen exactamente: $R(3,3)=6$, $R(3,4)=9$, $R(3,5)=14$, $R(3,6)=18$, $R(4,4)=18$, $R(4,5)=25$.

Ramsey en olimpiadas: cómo disfrazar la teoría

En los concursos, los problemas de tipo Ramsey raramente dicen "aplica el Teorema de Ramsey". Aparecen bajo disfraces como: coloraciones de aristas de grafos completos, relaciones de amistad entre grupos de personas, configuraciones de puntos coloreados, o particiones de enteros con propiedades algebraicas.

La señal de alerta más confiable es la frase "para cualquier configuración / coloración / partición, siempre existe...". Cuando el enunciado te pide demostrar que una estructura monocromática o con cierta propiedad es inevitable, piensa en Ramsey.

Patrón típico de solución: (1) identifica los "objetos" (vértices del grafo) y las "relaciones" (aristas con colores), (2) determina qué estructura monocromática buscas ($K_s$ o $K_t$), (3) usa la recurrencia o el argumento directo de paloma. Para cotas inferiores, construye explícitamente la coloración adversaria: suele ser un grafo circulante o el complemento de un grafo conocido.

Ejemplo de metamorfosis: "En un torneo de 6 jugadores donde todo par juega exactamente una vez, hay tres jugadores donde el resultado entre ellos es "todos ganaron a uno específico" (triángulo transitivo) o "ciclo de victorias" (triángulo cíclico)." Esto es exactamente $R(3,3) = 6$ con aristas orientadas, porque toda orientación de $K_6$ contiene un triángulo transitivo. La orientación de aristas es la "2-coloración" disfrazada.

El teorema de Schur y los parientes de Van der Waerden

Ramsey no está solo. Toda una familia de teoremas sigue el mismo patrón: en particiones suficientemente grandes, aparece una estructura algebraica o combinatoria definida.

Teorema de Schur (1916). Para todo $r \ge 1$, existe $S(r)$ tal que si los enteros $\{1, 2, \ldots, S(r)\}$ se colorean con $r$ colores, hay una solución monocromática de $x + y = z$. Por ejemplo, $S(2) = 5$: en cualquier 2-coloración de $\{1,2,3,4,5\}$, hay $x, y, z$ del mismo color con $x+y=z$. El teorema de Schur se deduce del de Ramsey aplicado al grafo de Schur.

Teorema de Van der Waerden (1927). Para todo $r \ge 1$ y todo $k \ge 1$, existe $W(r,k)$ tal que cualquier $r$-coloración de $\{1, 2, \ldots, W(r,k)\}$ contiene una progresión aritmética de longitud $k$ monocromática. Es decir: no se pueden colorear los enteros con finitos colores evitando infinitas progresiones aritméticas monocromáticas. El Teorema de Van der Waerden es estrictamente más difícil que el de Ramsey finito.

La conexión profunda: todos estos teoremas son instancias de un metateorema llamado "Teorema de Hales–Jewett", que dice que en cualquier coloración finita de un espacio de combinatorias suficientemente grande, hay una "línea combinatoria" monocromática. El Teorema de Ramsey, Schur y Van der Waerden son corolarios de Hales–Jewett. Para la olimpiada, lo que importa es reconocer que todos comparten la misma estructura conceptual: la inevitabilidad del orden.

Estrategia de competencia: construir y destruir

En competencias, los problemas de tipo Ramsey se presentan en dos modalidades: demostrar que una configuración es inevitable (cota superior) o construir una configuración que la evite (cota inferior / ejemplo extremal).

Para cotas superiores (inevitabilidad): el argumento más efectivo es el de paloma inductivo. Toma un vértice, divide su vecindad por color, aplica recurrencia. Si el problema tiene estructura algebraica, busca un argumento directo usando residuos, paridad u otro invariante modular.

Para cotas inferiores (construcciones explícitas): los grafos circulantes son tus mejores aliados. El grafo circulante $C_n(S)$ con conjunto de diferencias $S \subset \{1, \ldots, \lfloor n/2 \rfloor\}$ tiene como vértices $\mathbb{Z}_n$ y conecta $i$ con $j$ si $|i-j| \bmod n \in S$. Muchas coloraciones Ramsey extremales son grafos circulantes o productos de ellos.

El truco del "Supongamos que no": cuando el problema pide demostrar existencia, asumir que no existe la estructura buscada y derivar una contradicción numérica (demasiados/pocos elementos en algún conjunto) es casi siempre el camino más limpio.

Señales de alerta en el enunciado: "para todo $n$ suficientemente grande", "sea $N$ una constante que depende solo de...", "demuestra que siempre existe", "no importa cómo se distribuyan/coloreen...". Cualquiera de estas frases es una invitación a pensar en Ramsey.