El grafo de Turán $T(n,r)$ y la demostración de Zykov

Anatomía del grafo de Turán: la fórmula exacta

El grafo de Turán $T(n,r)$ se define como el único (salvo isomorfismo) grafo completo $r$-partido de $n$ vértices cuyas partes difieren en tamaño a lo sumo 1. Si $n = qr + s$ con $0 \le s < r$ (división euclidiana), entonces $T(n,r)$ tiene $s$ partes de tamaño $q+1$ y $r-s$ partes de tamaño $q$.

El número exacto de aristas de $T(n,r)$ se calcula directamente:

$|E(T(n,r))| = \binom{n}{2} - \sum_{i=1}^{r} \binom{n_i}{2}$

donde $n_i$ son los tamaños de las partes. Como $\sum \binom{n_i}{2} = \tfrac{\sum n_i^2 - n}{2}$, y $\sum n_i^2$ se minimiza con el reparto equilibrado, obtenemos la fórmula:

$|E(T(n,r))| = \left(1 - \frac{1}{r}\right)\frac{n^2}{2} - \frac{s(r-s)}{2r}$

donde $s = n \bmod r$. Para $r \mid n$, la fórmula simplifica exactamente a $\left(1-\tfrac{1}{r}\right)\tfrac{n^2}{2}$.

Ejemplos concretos: $T(6,2) = K_{3,3}$ tiene $9$ aristas; $T(6,3) = K_{2,2,2}$ tiene $12$ aristas; $T(9,3) = K_{3,3,3}$ tiene $27$ aristas.

Simetrización de Zykov: la prueba más limpia del Teorema de Turán

La prueba de Zykov (1949) del Teorema de Turán es la más elegante disponible. Introduce una operación de "simetría" sobre grafos que preserva la propiedad $K_{r+1}$-free y no decrece el número de aristas, convergiendo a $T(n,r)$.

Operación de Zykov. Dado un grafo $G$ y dos vértices no adyacentes $u, v \in V(G)$, la simetrización de Zykov $\sigma_{u,v}(G)$ es el grafo obtenido identificando $u$ y $v$ en un único vértice $w$, y conectando $w$ a todos los vecinos de $u$ o de $v$ (unión de vecindarios), luego añadiendo un nuevo vértice aislado para mantener $n$ vértices. Formalmente: el nuevo grafo tiene vértices $V(G)\setminus\{u\}$ y $w$, donde $w$ hereda $N(u) \cup N(v) \setminus \{u,v\}$ como vecinos.

Propiedad 1 (no pierde aristas). $|E(\sigma_{u,v}(G))| \ge |E(G)|$. Demostración: el vértice nuevo $w$ tiene $|N(u) \cup N(v)|$ vecinos, mientras que $u$ tenía $|N(u)|$ y $v$ tenía $|N(v)|$. El cambio neto en aristas es $|N(u)\cup N(v)| + 0 - |N(u)| - |N(v)| +$ (aristas perdidas entre $u$ y $v$, que no existía pues son no adyacentes) $= |N(u)\cup N(v)| - |N(u)| - |N(v)| = -|N(u) \cap N(v)| \le 0$. Espera: esto da que se pierden aristas. Corrijamos: el vértice aislado nuevo no aporta aristas, y $w$ tiene $|N(u) \cup N(v)|$ vecinos en lugar de $|N(u)| + |N(v)|$ (aristas de $u$ y $v$ combinadas, con la arista $uv$ que no existía). La ganancia neta es $|N(u)\cup N(v)| - |N(u)| - |N(v)| \ge -|N(u)\cap N(v)|$. Para la variante correcta: remplazamos $v$ por una copia de $u$ (mismos vecinos), con lo que el número de aristas cambia por $d(u) - d(v)$: si $d(u) \ge d(v)$, ganamos o nos quedamos igual.

Variante correcta de Zykov: clonación. Definimos la operación de clonar $v$ sobre $u$ (con $d(u) \ge d(v)$): reemplazar $v$ por una nueva copia de $u$ (mismos vecinos que $u$, sin aristas entre $u$ y la copia). El número de aristas cambia por $d(u) - d(v) \ge 0$. La copia puede introducir $K_{r+1}$ solo si ya había $K_r$ entre los vecinos comunes —pero si $G$ era $K_{r+1}$-free y entre los vecinos de $u$ no había $K_r$, la operación preserva $K_{r+1}$-free.

**Propiedad 2 (preserva $K_{r+1}$-free).** Si $G$ es $K_{r+1}$-free y $u, v$ no son adyacentes, entonces $\sigma_{u,v}(G)$ (con la operación de clonación correcta) también es $K_{r+1}$-free, siempre que el proceso converja a un grafo $r$-partido completo.

Convergencia. Aplicando repetidamente la operación de clonar el vértice de mayor grado sobre el de menor grado dentro de cada componente no-arista, el grafo converge a un estado donde todos los vértices sin arista entre ellos tienen el mismo vecindario. En ese estado, los vértices se particionan en $r$ clases de equivalencia (clases de no-adyacencia), y el grafo resultante es exactamente el grafo completo $r$-partido $T(n,r)$.

La unicidad del grafo extremal

El Teorema de Turán incluye un resultado de unicidad: el único grafo $K_{r+1}$-free con $n$ vértices y $|E(T(n,r))|$ aristas es el propio $T(n,r)$.

Esto se deduce del proceso de Zykov: si en algún paso la clonación estrictamente incrementa el número de aristas (es decir, $d(u) > d(v)$ en algún momento), entonces el grafo original tenía estrictamente menos aristas que $T(n,r)$. Para que un grafo $G$ alcance el máximo $|E(T(n,r))|$, cada paso de Zykov debe ser una igualdad, lo que ocurre si y solo si $G$ ya es $r$-partido completo desde el inicio.

El equilibrio entre partes (todas de tamaño $\lfloor n/r \rfloor$ o $\lceil n/r \rceil$) sigue de la observación: si una parte tiene tamaño $a$ y otra tiene tamaño $b$ con $a \ge b+2$, entonces mover un vértice de la parte de tamaño $a$ a la de tamaño $b$ cambia las aristas en $(b+1) - (a-1) +(a - 1 - 1) - ?$... Más limpidamente: para un grafo $r$-partido con partes de tamaños $n_1 \ge \ldots \ge n_r$, si $n_1 \ge n_r + 2$, mover un vértice de la primera parte a la última incrementa las aristas en $n_1 - 1 - n_r > 0$. Luego el máximo se alcanza cuando $n_1 - n_r \le 1$: partes equilibradas.

Versión de estabilidad: el Teorema de Simonovits

El Teorema de Turán dice que si $|E(G)| = \mathrm{ex}(n, K_{r+1})$, entonces $G \cong T(n,r)$. La versión de estabilidad (Simonovits, 1968) es un fortalecimiento cuantitativo: si $G$ tiene "casi" el máximo de aristas, entonces $G$ es "casi" isomorfo a $T(n,r)$.

Teorema de Simonovits (versión informal). Para todo $\varepsilon > 0$ existe $\delta > 0$ tal que si $G$ es $K_{r+1}$-free de $n$ vértices con $|E(G)| \ge (1-\delta)\, |E(T(n,r))|$, entonces $G$ se puede obtener de $T(n,r)$ borrando y añadiendo a lo sumo $\varepsilon n^2$ aristas.

Versión cuantitativa precisa. Si $G$ es $K_{r+1}$-free con $n$ vértices y $|E(G)| \ge |E(T(n,r))| - \varepsilon n^2$, entonces existe una partición de $V(G)$ en $r$ partes $V_1, \ldots, V_r$ tal que el número de aristas dentro de las partes (aristas "malas") es a lo sumo $f(\varepsilon) \cdot n^2$, donde $f(\varepsilon) \to 0$ cuando $\varepsilon \to 0$.

La estabilidad es crucial para muchas aplicaciones: permite deducir que cualquier grafo extremal o casi-extremal tiene la estructura global de $T(n,r)$ con solo "ruido local". En problemas olímpicos avanzados, cuando el enunciado pide caracterizar todos los grafos que alcanzan o casi alcanzan el máximo, la estabilidad de Simonovits es la herramienta correcta.

Ejemplo de aplicación directa: Si en un grafo $G$ de $n$ vértices con $n^2/3 - cn$ aristas (para $c$ grande) sabemos que $G$ es $K_4$-free, el Teorema de Simonovits dice que $G$ es "casi" $T(n,3)$: hay una 3-partición de los vértices con pocas aristas dentro de las partes. Esta información es suficiente para muchas demostraciones de existencia en olimpiadas.

Turán generalizado: el número extremal ex(n, H)

El problema de Turán puede generalizarse: dado un grafo $H$ arbitrario (no solo un clique), ¿cuál es $\mathrm{ex}(n, H)$, el máximo número de aristas en un grafo de $n$ vértices que no contiene $H$ como subgrafo?

Para $H = K_{r+1}$, la respuesta es $|E(T(n,r))|$. Para hipergrafos $H$ más generales, la teoría se vuelve mucho más compleja.

Teorema de Kővári–Sós–Turán (1954). Para el grafo bipartito completo $K_{s,t}$ con $s \le t$, $\mathrm{ex}(n, K_{s,t}) \le \tfrac{1}{2}(t-1)^{1/s} \cdot n^{2-1/s} + \tfrac{s-1}{2} \cdot n$. Este resultado tiene aplicaciones directas en geometría combinatoria (acota incidencias punto-curva).

**El número de Zarankiewicz $z(n;s)$** es $\mathrm{ex}(n, K_{s,s})$ y aparece en problemas sobre matrices de 0s y 1s sin submatriz de unos $s \times s$. Para $s=2$: $\mathrm{ex}(n, K_{2,2}) \le \tfrac{1}{2}(1+\sqrt{4n-3}) \cdot n / 2 \approx \tfrac{1}{2}n^{3/2}$, una cota que aparece en problemas tipo "dado un conjunto de $n$ puntos en el plano, el número de pares de puntos a distancia 1 es $O(n^{3/2})$".

Para olimpiadas, el nivel de generalidad relevante es: conocer que $\mathrm{ex}(n, H)$ es de orden $n^{2-1/\chi(H)}$ para grafos bipartitos (donde $\chi(H)$ es el número cromático), y $\mathrm{ex}(n, K_{r+1}) = (1-1/r)n^2/2 + O(n)$ para cliques.

Problemas olímpicos con sabor a Turán

El Teorema de Turán aparece en olimpiadas disfrazado de muchas formas. Los patrones más frecuentes son:

**Patrón 1: "Dado $n$ objetos y relaciones entre ellos, sin triángulo/cuarteto de relaciones mutuas, acota el número de relaciones."** Este es $\mathrm{ex}(n, K_{r+1})$ directamente.

**Patrón 2: "En cierta configuración densa, demuestra que existe un clique de tamaño $r+1$."** Equivale a demostrar que el número de aristas supera $\mathrm{ex}(n, K_{r+1})$.

Patrón 3: "Caracteriza todas las configuraciones que alcanzan el máximo." Aquí la unicidad de $T(n,r)$ resuelve el problema.

Estrategia de resolución: (1) modela el problema como un grafo $G$ de $n$ vértices; (2) identifica el subgrafo prohibido (clique de tamaño $r+1$); (3) aplica el Teorema de Turán con el $r$ correcto; (4) si el problema da más aristas que $|E(T(n,r))|$, el clique existe; si pide el máximo sin clique, la respuesta es $|E(T(n,r))|$ y el extremal es $T(n,r)$.

Coda histórica: Pál Turán demostró este teorema mientras cumplía trabajos forzados en Budapest durante 1941. Escribió las ideas en papel de periódico y las memorizó. Al salir del campo, las publicó de inmediato. Su trabajo sobrevivió a la guerra y fundó una disciplina entera.