Ramsey finito

El problema de los amigos y desconocidos

En una fiesta de 6 personas, ¿es siempre cierto que hay 3 que se conocen entre sí mutuamente, o 3 que son mutuamente desconocidos? La respuesta, sorprendentemente, es sí.

Este es el Teorema de Ramsey en su versión más elemental. Formalizado: en cualquier 2-coloración de las aristas de $K_6$ (grafo completo en 6 vértices) con colores rojo y azul, existe un triángulo monocromático (todo rojo o todo azul).

La idea general es que el orden impone estructura. Con suficientes vértices, siempre aparece un subgrafo completo monocromático de cualquier tamaño predeterminado. Frank Ramsey probó esto en 1930.

Prueba de $R(3,3) \le 6$

Sea $G = K_6$ con aristas coloreadas de rojo o azul. Fija un vértice $v$. Tiene 5 vecinos, y las 5 aristas desde $v$ son rojas o azules.

Por el principio del palomar: de 5 aristas y 2 colores, al menos $\lceil 5/2 \rceil = 3$ aristas tienen el mismo color. Supongamos sin pérdida de generalidad que hay 3 aristas rojas: $\{v, a\}$, $\{v, b\}$, $\{v, c\}$ son rojas.

Ahora considera las aristas entre $a$, $b$, $c$. Si alguna es roja —digamos $\{a, b\}$— entonces $\{v, a, b\}$ forma un triángulo rojo. Si ninguna es roja, entonces las tres aristas $\{a,b\}$, $\{a,c\}$, $\{b,c\}$ son azules, formando un triángulo azul.

En ambos casos existe un triángulo monocromático. Como $v$ fue arbitrario, esto vale para toda 2-coloración de $K_6$.

La cota superior de Erdős-Szekeres

El número de Ramsey $R(s,t)$ es el menor $n$ tal que toda 2-coloración de las aristas de $K_n$ contiene un clique rojo de tamaño $s$ o un clique azul de tamaño $t$.

Una cota superior elemental: $R(s,t) \le R(s-1,t) + R(s,t-1)$. Esto se demuestra igual que el argumento de $R(3,3)$: fija un vértice $v$ con $n-1$ vecinos. Si hay al menos $R(s-1,t)$ aristas rojas desde $v$, por definición existe un clique rojo de $s-1$ (que junto con $v$ da $s$) o un clique azul de $t$. Similarmente si hay al menos $R(s,t-1)$ aristas azules.

Combinando, $R(s,t) \le R(s-1,t) + R(s,t-1)$, y con los casos base $R(1,t) = 1$ y $R(s,1) = 1$, se obtiene por inducción:

Valores conocidos y el problema de la aguja en el pajar

Los únicos valores de $R(s,t)$ que se conocen exactamente son muy pocos. Los más relevantes para olimpiadas:

$R(3,3) = 6$: probado arriba. La construcción que muestra $R(3,3) > 5$ es el ciclo $C_5$ coloreado: 2-colorar las aristas de $K_5$ de modo que ni el pentágono ni el pentágono cruzado sea monocromático.

$R(3,4) = 9$: toda 2-coloración de $K_9$ tiene un triángulo rojo o un $K_4$ azul.

$R(4,4) = 18$: conocido, pero su prueba es una verificación computacional extensa.

El problema de determinar $R(5,5)$ sigue abierto. Erdős bromeó: si una civilización alienígena amenazara destruir la Tierra a menos que encontráramos $R(5,5)$, sería mejor tratar de atacar.

Para la ONEM regional basta conocer $R(3,3) = 6$ y la cota $R(s,t) \le \binom{s+t-2}{s-1}$.

Aplicaciones directas en olimpiadas

Los problemas regionales de tipo Ramsey suelen aparecer bajo disfraces: "en una reunión de $n$ personas, siempre hay 3 que se conocen o 3 que no se conocen" ($n=6$), o problemas de coloración de segmentos, puntos en el plano, o números.

La clave es reconocer que el problema pide un subconjunto monocromático y modelarlo como una 2-coloración de aristas de $K_n$. Una vez en ese lenguaje, la prueba por palomar funciona.

Variante frecuente: "en un torneo de ajedrez con $n$ jugadores, hay 3 que se ganaron mutuamente en ciclo o 3 que perdieron entre sí mutuamente". Este es el Teorema de Ramsey para torneos, con $n = 6$ siendo suficiente.