Desigualdades de Turán en problemas olímpicos

El diccionario: de enunciado olímpico a teorema de Turán

La primera habilidad en la resolución de problemas extremales es la traducción fiel del enunciado al lenguaje de la teoría de grafos extremal. Presentamos el diccionario fundamental.

**"$n$ elementos con relaciones binarias"** → vértices del grafo $G$, con cada relación como arista.

**"Sin $k$ elementos mutuamente relacionados"** → $G$ es $K_k$-free, luego $|E(G)| \le |E(T(n,k-1))|$.

**"Al menos $m$ relaciones"** con $m > |E(T(n,k-1))|$ → existe $K_k$ (Turán inverso).

**"Relaciones entre dos grupos distintos $A$ y $B$"** → el grafo es bipartito $G \subseteq K_{|A|,|B|}$, y Kővári–Sós–Turán aplica si se prohíbe $K_{s,t}$.

**"Para todo $x$ hay a lo sumo $d$ elementos relacionados con $x$"** → $\Delta(G) \le d$, el grado máximo está acotado, y la combinación con Turán da cotas más finas.

El paso más delicado es identificar el parámetro $r$ correcto (el $r$ en $K_{r+1}$ prohibido). Una buena heurística: si el problema prohíbe $k$ objetos "mutuamente relacionados", entonces $r = k-1$. Si la restricción es más compleja (por ejemplo, "sin $k$ objetos de los cuales todo par tiene cierta propiedad especial"), puede ser necesario reformular.

Problema resuelto: máximo de relaciones sin triángulo

Problema. En una clase de $n$ estudiantes, se define una relación "colaboración" entre pares de estudiantes. Supón que ningún grupo de tres estudiantes tiene colaboraciones mutuas entre todos los pares (sin triángulo de colaboraciones). ¿Cuál es el máximo número de colaboraciones posibles, y cuándo se alcanza?

Traducción. El grafo $G$ de colaboraciones es $K_3$-free (sin triángulos). Queremos maximizar $|E(G)|$ con $|V(G)| = n$.

Solución por Turán. El Teorema de Turán con $r=2$ da $|E(G)| \le |E(T(n,2))| = \lfloor n^2/4 \rfloor$. El máximo se alcanza en $T(n,2) = K_{\lfloor n/2 \rfloor, \lceil n/2 \rceil}$.

Descripción del extremal. Dividir los $n$ estudiantes en dos grupos de tamaño $\lfloor n/2 \rfloor$ y $\lceil n/2 \rceil$, y definir colaboración entre todo par de estudiantes de distintos grupos (nadie colabora con alguien del mismo grupo). Esta configuración tiene $\lfloor n^2/4 \rfloor$ colaboraciones y no tiene triángulo (el grafo es bipartito). Es la única configuración maximal (salvo la elección de los grupos cuando $n$ es par, en cuyo caso hay $\binom{n}{n/2}/2$ configuraciones no isomorfas —pero todas son isomorfas como grafos).

Refinamiento. Si $n = 2k$, el máximo es $k^2$, alcanzado por $K_{k,k}$. Si $n = 2k+1$, el máximo es $k(k+1)$, alcanzado por $K_{k,k+1}$.

Problema resuelto: contando diagonales prohibidas

Problema (IMO Shortlist 2016 C1, adaptado). Sea $n \ge 4$. En una reunión de $n$ personas, llamamos "tríada activa" a todo conjunto de tres personas $\{A, B, C\}$ tal que $A$ conoce a $B$, $B$ conoce a $C$, y $A$ conoce a $C$ (conocimiento mutuo). Si hay exactamente $k$ tríadas activas, ¿qué valores de $k$ son posibles? ¿Cuál es el mínimo número de "conocidos" (aristas) necesario para tener al menos una tríada activa?

Traducción. Una "tríada activa" es un triángulo en el grafo $G$ de "conocidos". El número de triángulos en $G$ es $k$.

Para la segunda parte: queremos el menor $|E(G)|$ tal que $G$ contiene al menos un triángulo. Por contrarrecíproco, si $G$ es $K_3$-free, entonces $|E(G)| \le \lfloor n^2/4 \rfloor$. Luego si $|E(G)| > \lfloor n^2/4 \rfloor$, hay al menos un triángulo. El mínimo de aristas para garantizar un triángulo es $\lfloor n^2/4 \rfloor + 1$.

Contando triángulos. El número de triángulos $T(G)$ en un grafo $G$ con grados $d_1, \ldots, d_n$ satisface $T(G) \le \sum_v \binom{d_v}{2}/3$ (cota por vértice: cada triángulo se cuenta tres veces). La fórmula exacta requiere conocer la estructura local: $T(G) = \frac{1}{6}(\mathrm{tr}(A^3))$ donde $A$ es la matriz de adyacencia.

Para $k = 0$ (sin triángulos), el grafo puede tener hasta $\lfloor n^2/4 \rfloor$ aristas. Para $k \ge 1$, la relación entre $k$ y el mínimo de aristas involucra el Teorema de Kruskal–Katona para hipergrafos 3-uniformes (contar 3-cliques como "celdas" del complejo simplicial).

El Teorema de Bondy–Simonovits y ciclos

Más allá de los cliques, el problema de Turán generalizado pregunta por $\mathrm{ex}(n, H)$ para grafos $H$ arbitrarios. El Teorema de Bondy–Simonovits (1974) da la respuesta asintótica para grafos con ciclos.

Teorema de Bondy–Simonovits. Para todo grafo $H$ con al menos una arista y número cromático $\chi(H) = r+1 \ge 2$,

$\mathrm{ex}(n, H) = \left(1 - \frac{1}{r}\right)\frac{n^2}{2} + o(n^2)$.

En particular, $\mathrm{ex}(n, H) = |E(T(n,r))| + o(n^2)$ cuando $\chi(H) = r+1$. El grafo de Turán sigue siendo extremal asintóticamente para cualquier subgrafo prohibido $H$ con número cromático $r+1$.

**Caso especial: ciclos pares $C_{2k}$.** Los ciclos pares son bipartitos ($\chi(C_{2k}) = 2$), así que $\mathrm{ex}(n, C_{2k}) = o(n^2)$. La cota exacta es $\mathrm{ex}(n, C_4) = \Theta(n^{3/2})$ (Reiman, 1958) y $\mathrm{ex}(n, C_6) = \Theta(n^{4/3})$ (Bondy-Simonovits para $C_6$ vía Kővári-Sós-Turán). Estos son usados en problemas de geometría combinatoria sobre incidencias.

**Caso especial: ciclos impares $C_{2k+1}$.** Los ciclos impares tienen $\chi = 3$, así que $\mathrm{ex}(n, C_{2k+1}) = (1-1/2) n^2/2 + o(n^2) = n^2/4 + o(n^2)$. Para $k=1$: $\mathrm{ex}(n, C_3) = \lfloor n^2/4 \rfloor$ (Teorema de Mantel, sin términos $o$).

La diferencia entre bipartito y no bipartito es esencial: la prohibición de un ciclo par es "mucho más restrictiva" (permite solo $O(n^{2-1/k})$ aristas) que la de un ciclo impar ($O(n^2)$ aristas).

Problemas con variantes bipartitas: el teorema de Kővári–Sós–Turán en acción

Problema. Sean $A$ y $B$ conjuntos de $n$ puntos cada uno en el plano. Cada punto de $A$ está conectado con exactamente $k$ puntos de $B$. ¿Cuántas veces puede ocurrir que dos puntos de $A$ compartan un mismo par de vecinos en $B$?

Traducción. El grafo bipartito $G \subseteq K_{n,n}$ tiene cada vértice de $A$ con grado exactamente $k$. Preguntar "cuántos pares de $A$ comparten dos vecinos en $B$" es preguntar cuántas copias de $K_{2,2}$ hay en $G$.

Solución por Kővári–Sós–Turán. El teorema da: si $G$ tiene $n$ vértices en cada parte y $e$ aristas, entonces el número de $K_{2,2}$ en $G$ es al menos $\tfrac{e}{4}\bigl(\tfrac{e}{n} - 1\bigr)$. Con $e = nk$ (pues cada vértice de $A$ tiene grado $k$): número de $K_{2,2} \ge \tfrac{nk}{4}(k-1)$.

Cota superior por Kővári–Sós–Turán. Si queremos que no haya $K_{2,2}$ (es decir, no hay dos puntos de $A$ con dos vecinos comunes en $B$), entonces $e \le \tfrac{1}{2}(1+\sqrt{4n-3})\cdot n/2 \approx \tfrac{1}{2}n^{3/2}$, lo que da $k \le \tfrac{1}{2}n^{1/2} + O(1)$.

Este tipo de argumento aparece en el IMO con disfraces como: "un comité de $n$ personas, cada persona conoce a exactamente $k$ otros, demuestra que si $k > \sqrt{n}$ entonces hay cuatro personas $A, B, C, D$ tales que $A$ y $B$ conocen a $C$ y $D$". La solución es exactamente Kővári–Sós–Turán.

Estrategia unificada para problemas extremales olímpicos

Concluimos con un esquema de ataque para problemas extremales en olimpiadas, integrado con todos los resultados del Capítulo 2.

Paso 1: Identificar el modelo. ¿El problema involucra $n$ objetos con relaciones binarias? → Grafo $G$ de $n$ vértices. ¿Las relaciones son entre dos grupos distintos? → Grafo bipartito. ¿Las relaciones son $k$-arias? → Hipergrafo $k$-uniforme (posiblemente Kruskal-Katona).

Paso 2: Identificar la restricción prohibida. ¿Qué subgrafo está prohibido (implícita o explícitamente)? Si el problema dice "sin $k$ objetos mutuamente relacionados", el subgrafo prohibido es $K_k$. Si dice "sin dos objetos con $s$ vecinos comunes", el subgrafo prohibido es $K_{2,s}$ o $K_{s,t}$.

Paso 3: Aplicar el teorema correcto. $K_{r+1}$ prohibido → Turán, extremal es $T(n,r)$. $K_{s,t}$ prohibido → Kővári-Sós-Turán, extremal es un grafo bipartito casi equilibrado. $H$ bipartito prohibido → Bondy-Simonovits, extremal es casi bipartito. $k$-conjuntos con sombra pequeña → Kruskal-Katona, extremal es el segmento inicial colex.

Paso 4: Verificar el extremal. Construir explícitamente el grafo o familia extremal y verificar que satisface la restricción y alcanza la cota. La unicidad del extremal es a menudo el núcleo de la demostración de caracterización.

Paso 5: Estabilidad si el problema lo requiere. Si el enunciado pide "caracteriza todos los grafos que alcanzan el máximo" o "demuestra que los grafos casi-extremales tienen cierta estructura", aplicar el Teorema de Simonovits o una variante ad hoc del argumento de compresión.

Este esquema es suficiente para el 90% de los problemas extremales de tipo grafos en el IMO, ISL y olimpiadas regionales. El 10% restante requiere herramientas más avanzadas como el Lema de Regularidad de Szemerédi (que veremos en el Capítulo 4) o el método de contenedores.