Ramsey, extremalidad y densidad de aristas

Orden inevitable: la filosofía de Ramsey

La teoría de Ramsey encarna una idea filosófica profunda: en todo sistema suficientemente grande, cierto orden es inevitable. No importa cómo distribuyas los elementos, si el sistema es lo bastante grande aparecerá la estructura que tratas de evitar. Esta idea aparece repetidamente en olimpiadas bajo disfraces variados: "demuestra que siempre existen 3 puntos con cierta propiedad", "demuestra que en cualquier coloración hay un monocromático".

El ejemplo prototípico ya lo vimos: $R(3,3) = 6$. En cualquier coloración rojo-azul de las aristas de $K_6$, hay un triángulo monocromático. La prueba usa el Principio de la Paloma en su forma más elegante: un vértice tiene 5 aristas, por lo que al menos 3 son del mismo color, y esas 3 aristas fuerzan el triángulo.

Pero la teoría de Ramsey va mucho más allá de triángulos. El Teorema de Ramsey (versión general) dice que para cualesquiera $s, t \geq 1$, el número de Ramsey $R(s,t)$ es finito: existe un $n$ tal que toda 2-coloración de $K_n$ contiene un clique rojo de tamaño $s$ o un clique azul de tamaño $t$. La prueba usa la recurrencia $R(s,t) \leq R(s-1,t) + R(s,t-1)$ y la inducción.

En olimpiadas de nivel IbAm, las aplicaciones de Ramsey más frecuentes son: (1) encontrar triángulos monocromáticos en coloraciones de aristas, (2) encontrar conjuntos independientes grandes, y (3) demostrar que cierta configuración geométrica siempre contiene un subconjunto con propiedades especiales.

Números de Ramsey: valores, cotas y técnicas

Los números de Ramsey $R(s,t)$ son notoriamente difíciles de calcular exactamente. Los valores conocidos son escasos: $R(3,3)=6$, $R(3,4)=9$, $R(3,5)=14$, $R(3,6)=18$, $R(4,4)=18$, $R(3,7)=23$. El valor de $R(5,5)$ sigue desconocido; se sabe que $43 \leq R(5,5) \leq 48$.

Cota superior general: La recurrencia $R(s,t) \leq R(s-1,t) + R(s,t-1)$ implica:

Prueba de la cota superior: Sea $n = R(s-1,t) + R(s,t-1)$. En $K_n$ con una 2-coloración, fijemos un vértice $v$. Sean $r$ y $b$ los grados rojo y azul de $v$; $r + b = n - 1$. Como $r + b = R(s-1,t) + R(s,t-1) - 1$, al menos uno de los siguientes vale: $r \geq R(s-1,t)$ o $b \geq R(s,t-1)$. En el primer caso, entre los $r$ vecinos rojos de $v$ hay un clique rojo de tamaño $s-1$ o uno azul de tamaño $t$; añadiendo $v$ al clique rojo obtenemos $K_s$ rojo. En el segundo caso, análogamente. $\square$

Cota inferior probabilística: Para demostrar $R(s,s) > n$, coloreamos las aristas de $K_n$ uniformemente al azar. La probabilidad de que un conjunto fijo de $s$ vértices forme un clique monocromático es $2 \cdot 2^{-\binom{s}{2}} = 2^{1-\binom{s}{2}}$. Por la desigualdad de la unión, la probabilidad de que exista algún clique monocromático es a lo más $\binom{n}{s} \cdot 2^{1-\binom{s}{2}}$. Si $\binom{n}{s} < 2^{\binom{s}{2}-1}$, esta probabilidad es menor que 1, luego existe una coloración sin clique monocromático. Esto da $R(s,s) > n$.

**Aplicación: $R(3,3) = 6$.** Ya probamos $R(3,3) \leq 6$ usando la recurrencia. Para ver que $K_5$ puede colorearse sin triángulo monocromático, tomamos el pentágono: las aristas del ciclo $C_5$ en rojo y las diagonales en azul. Los subgrafos rojo y azul son ambos $C_5$, que no contiene triángulos. Esto muestra $R(3,3) > 5$, luego $R(3,3) = 6$.

Extremalidad: el principio del caso extremo

El principio de extremalidad dice: cuando necesites demostrar que algo existe, elige el objeto "más extremo" disponible (el vértice de mayor grado, el camino más largo, el conjunto más grande con cierta propiedad) y extrae consecuencias del hecho de que no puede ser "mejorado".

Ejemplo fundamental: En todo grafo $G$ con grado mínimo $\delta(G) \geq k$, existe un camino de longitud al menos $k$. Prueba: sea $P = v_0, v_1, \ldots, v_\ell$ el camino más largo de $G$. Todos los vecinos de $v_\ell$ deben estar en $P$ (si hubiera un vecino $w \notin V(P)$, podríamos extender $P$ añadiendo la arista $v_\ell$-$w$, contradiciendo la maximalidad). Como $d(v_\ell) \geq k$, hay al menos $k$ vecinos de $v_\ell$ en $P$, luego $\ell \geq k$. $\square$

Ejemplo de ciclo: En todo grafo $G$ con $\delta(G) \geq 2$, existe un ciclo. Prueba: sea $P = v_0, v_1, \ldots, v_\ell$ el camino más largo. Como antes, todos los vecinos de $v_\ell$ están en $P$. Como $d(v_\ell) \geq 2$, $v_\ell$ tiene un vecino $v_i$ con $i \leq \ell - 2$ (además de $v_{\ell-1}$). El ciclo $v_i, v_{i+1}, \ldots, v_\ell, v_i$ existe. $\square$

Técnica del "elemento más especial": En problemas donde el conjunto de objetos tiene una medida natural (longitud de un camino, suma de pesos, número de aristas incidentes), el elemento que maximiza o minimiza esa medida suele tener propiedades que se pueden explotar directamente. La clave es identificar la medida correcta y el tipo de extremo (máximo o mínimo) adecuado.

Problema olímpico (Cono Sur 2018, P3, adaptado): En un torneo con $n$ equipos, el equipo $A$ se llama "campeón" si para todo equipo $B$, o bien $A$ le ganó a $B$ directamente, o existe $C$ tal que $A$ le ganó a $C$ y $C$ le ganó a $B$. Demuestra que siempre hay al menos un campeón. Solución: sea $W$ el equipo con más victorias (máximo $d^+(W)$). Para cualquier equipo $X$ que le ganó a $W$: si algún $Z$ con $W \to Z$ tiene $Z \to X$, entonces $W$ domina a $X$. Si no existe tal $Z$, entonces $X$ venció a todos los equipos en $N^+(W)$, dando a $X$ al menos $|N^+(W)| + 1 > d^+(W)$ victorias, contradiciendo la maximalidad. $\square$

Densidad de aristas y el Teorema de Turán

Una pregunta fundamental en la teoría extremal de grafos es: ¿cuántas aristas puede tener un grafo con $n$ vértices que no contiene $K_{r+1}$ como subgrafo? La respuesta la da el Teorema de Turán.

**Grafo de Turán $T(n,r)$:** Para $n,r \geq 1$, el grafo de Turán $T(n,r)$ se obtiene partiendo los $n$ vértices en $r$ grupos lo más iguales posible (grupos de tamaño $\lfloor n/r \rfloor$ o $\lceil n/r \rceil$) y conectando todos los pares de vértices en grupos distintos. Este grafo es $(r-1)$-partito completo y tiene exactamente:

Teorema de Turán: Si $G$ es un grafo simple con $n$ vértices que no contiene $K_{r+1}$ como subgrafo, entonces $|E(G)| \leq |E(T(n,r))|$. Además, el grafo de Turán $T(n,r)$ es el único extremal (el único que alcanza la cota).

**Prueba simplificada para $r=2$ (sin triángulos):** Si $G$ tiene $n$ vértices y no contiene $K_3$ (triángulo), entonces $|E(G)| \leq \lfloor n^2/4 \rfloor$. Prueba: sea $u$ el vértice de mayor grado $\Delta = d(u)$. Como $G$ no tiene triángulos, los $\Delta$ vecinos de $u$ no tienen aristas entre ellos; cada vecino de $u$ está conectado sólo a los $n - 1 - \Delta$ no-vecinos de $u$. Por tanto $|E(G)| \leq \Delta(n - \Delta) + \Delta \leq \Delta(n - \Delta) + \Delta$. La función $\Delta(n - \Delta)$ se maximiza en $\Delta = n/2$, dando $n^2/4$. Contando la arista $u$-$v$ en $E$: $|E| \leq n^2/4$. $\square$

**Número de Turán $ex(n, H)$:** Para un grafo $H$, el extremal $ex(n,H)$ es el máximo número de aristas en un grafo con $n$ vértices que no contiene $H$ como subgrafo. El Teorema de Turán calcula $ex(n, K_{r+1})$. Para otros subgrafos $H$, el problema es más difícil: por ejemplo, $ex(n, C_4) = \Theta(n^{3/2})$.

Aplicaciones combinadas en problemas de olimpiada

En las olimpiadas de nivel Iberoamericano, los problemas de grafos que puntúan más alto suelen combinar varias herramientas: un argumento de Ramsey para mostrar que cierta estructura existe, un principio de extremalidad para identificar el "lugar" de esa estructura, y una cota de densidad para acotar cuántas veces puede ocurrir.

Problema representativo (IbAm 2011, P4): Sea $G$ un grafo con $n$ vértices y más de $n^2/4$ aristas. Demuestra que $G$ contiene un triángulo. Solución directa: por el Teorema de Turán con $r=2$, $ex(n, K_3) = \lfloor n^2/4 \rfloor$. Como $|E(G)| > n^2/4 \geq \lfloor n^2/4 \rfloor$, el grafo $G$ debe contener un triángulo. $\square$

Problema con extremalidad y Ramsey combinados (Cono Sur 2020, P2, adaptado): En una competencia con $n$ países, cada par de países intercambió exactamente un regalo (dirigido: $A$ le da a $B$ o $B$ le da a $A$). Demuestra que existe un conjunto de 3 países que forman un "ciclo de regalos" (A le da a B, B le da a C, C le da a A). Solución: modela el intercambio como un torneo dirigido. El país con más regalos enviados $W$ tiene $d^+(W) \geq (n-1)/2$ países que recibieron de $W$. Entre esos países, si algún par $(X, Y)$ tiene $X$ enviando a $Y$ y $Y$ enviando a $W$: el triple $(W, X, Y)$ forma... no exactamente. Revisamos: si $X \to Y$ y $Y \to W$ y $W \to X$, tenemos el ciclo $(W \to X \to$... hmm. El argumento correcto es: $W \to X$, $W \to Y$, y si $X \to Y$ entonces no hay ciclo directo. Pero entre los $d^+(W)$ receptores de $W$, si ningún par forma un ciclo con $W$, todos esos pares $X,Y$ tienen $Y \to X$ (sin ciclos en esa dirección). Eso crea un torneo sin ciclo entre los receptores, que tiene orden topológico. En el fondo, se usa que todo torneo tiene un ciclo hamiltoniano o una fuente, y el argumento se apoya en $R(3,3)=6$ para $n \geq 6$.

Estrategia integrada: (1) Verifica si el problema tiene una estructura de coloración (bipartición / Ramsey). (2) Si el problema pide existencia, aplica extremalidad: elige el objeto con la propiedad máxima y derívala. (3) Si el problema pide una cota superior sobre el número de aristas, recuerda que $ex(n, K_3) = \lfloor n^2/4 \rfloor$ y que en general grafos sin $K_{r+1}$ tienen a lo más $(1 - 1/r) n^2/2$ aristas. (4) Combina las herramientas en el orden que corresponda a la lógica del problema.

Errores comunes y cómo evitarlos: (a) Confundir $R(s,t)$ con la cota: $R(3,3)=6$ significa que en $K_6$ siempre hay triángulo monocromático, y en $K_5$ puede no haberlo; no que en $K_6$ "siempre hay 6 triángulos". (b) Olvidar que el Teorema de Turán da una cota para $|E|$, no para el número de cliques. (c) En extremalidad, no verificar que el objeto "más extremo" realmente satisface las hipótesis del problema antes de extraer consecuencias.

Resumen del Capítulo 1: Con el Lema del Apretón de Manos, árboles y árboles generadores, 2-coloración y grafos bipartitos, y la triada Ramsey-Extremalidad-Turán, tienes el toolkit completo para resolver el 80% de los problemas de grafos en olimpiadas Cono Sur e Iberoamericana. El 20% restante requiere el Teorema de Hall (Capítulo 5) o coloraciones más finas (Capítulo 2), pero siempre sobre esta base.