El teorema de Turan: el comienzo de la teoría de grafos extrema

A estas alturas de la película creo que a pocos se les escapará que la teoría de grafos es muy importante en la actualidad: su utilización en redes, comunicación, biología o sociología hacen de esta rama de las matemáticas una herramienta esencial para el estudio y la modelización de muchos aspectos de nuestra vida.

Históricamente, se considera el estudio y resolución del problema de los puentes de Königsberg por parte de Leonhard Euler como el comienzo de la teoría de grafos. Hoy vamos a hablar del nacimiento de una parte de ella, la teoría de grafos extrema, y del resultado a partir del cual comenzó su estudio, el teorema de Turan.

Paul Turán

Comencemos por el principio: la teoría de grafos extrema es la parte de la teoría de grafos que estudia los casos extremos o límite que pueden darse en grafos con ciertas propiedades. Es decir, se fija una propiedad de un grafo y se buscan los casos extremos (máximo o mínimo) de las características de dicho grafo bajo la imposición inicial.

Y, como decíamos antes, se establece el comienzo de esta parte de la teoría de grafos en 1941, año en el que Paul Turán demostró su teorema. Paul Turán fue un matemático húngaro que se dedicó principalmente a la teoría de números y a la teoría de grafos y que colaboró durante mucho tiempo con el gran Paul Erdös.

Antes de ver de qué trata el teorema de Turán, y partiendo de que sabemos que un grafo es un conjunto no vacío de vértices y conjunto de aristas que unen vértices, vamos a recordar un concepto que aparece en él: grafo completo. Un grafo completo de $p$ vértices, que suele representarse por $K_p$ , es un grafo en el que cada uno de esos $p$ vértices está unido con todos los demás por una arista (ya lo explicábamos aquí y aquí, pero no está de más recordarlo). Aquí tenéis unas representaciones gráficas amigables de $K_3, K_4$ y $K_5$

Ya estamos preparados para meternos en el teorema de Turán. Turán se preguntó algo relacionado con los grafos no dirigidos que no contengan un $K_p$ como subgrafo. Un subgrafo de este tipo se denomina $p$ -clique o $p$ -clan. Haciendo honor al libro del cual he tomado la demostración aquí utilizaré la segunda forma. Bien, la pregunta de Turán fue la siguiente:

Imaginemos que tenemos un grafo simple (esto es, no tiene lazos ni más de una arista uniendo una pareja de vértices) que no contiene un $p$ -clan. ¿Cuántas aristas, como máximo, puede tener este grafo?

La primera cuestión a comentar es que es bastante sencillo encontrar grafos que no contengan un $p$ -clan. Simplemente dividimos el conjunto de vértices $V$ (que suponemos con $n$ vértices) en $p-1$ conjuntos disjuntos dos a dos, $V_1, \ldots , V_{p-1}$ , y conectamos dos vértices si y sólo si están en conjuntos distintos $V_i, V_j$ . Por ejemplo, si queremos encontrar un grafo que no contenga un 3-clan (vamos, un triángulo), dividimos los vértices del mismo en 2 conjuntos y unimos cada vértice de uno de ellos con todos los vértices del otro. Por poner un ejemplo, si el número de vértices del grafo inicial es 6, el grafo resultante es el denominado $K_{3,3}$ :

Vamos a meternos algo más en el estudio del número de aristas. Si fijamos el valor de $n$ , el mayor número de aristas para estos grafos si los tamaños de los conjuntos $V_i$ (llamemos a su número de vértices $n_i$ ) son tan parecidos como sea posible, es decir, si son iguales o difieren en una unidad para cualquier pareja (o lo que es lo mismo, $|n_i-n_j| \leq 1$ , para todo $i,j$ ). Estos grafos se denominan grafos de Turán.

La cosa es que si se diera el caso de que $p-1$ es un divisor de $n$ , el número de aristas del grafo es conocido, e igual a

$\left ( 1- \cfrac{1}{p-1} \right ) \cdot \cfrac{n^2}{2}$

Pues el teorema de Turán dice que ese número es una cota superior para todo grafo con $n$ vértices que no contenga un $p$ -clan. Lo enunciamos:

Teorema de Turán

Si un grafo $G$ con $n$ vértices no contiene un $p$ -clan, entonces el máximo número de aristas que puede tener dicho grafo es

$\left ( 1- \cfrac{1}{p-1} \right ) \cdot \cfrac{n^2}{2}$

Antes de conocerse demostración para este teorema lo que se conocían eran demostraciones para el caso $p=3$ (el caso $p=2$ es trivial). Aquí vamos a ver una demostración del propio Turán que usa inducción, aunque es interesante resaltar que se conocen demostraciones muy variadas del mismo. Vamos con ella:

Demostración:

Vamos a hacer inducción sobre el número de vértices, $n$ , del grafo inicial.

Es fácil ver que el resultado es cierto si $n < p$ , ya que si fuera así el número máximo de aristas de $G$ sería ${n \choose 2}$ (es decir, si $G$ fuera el grafo completo de $n$ vértices), y ese número es menor que la cota que propone el teorema). Supongamos entonces que $G$ tiene $n$ vértices, con $n \geq p$ , que no contiene un $p$ -clan y que tiene el mayor número de aristas posible.

Está claro entonces que $G$ debe contener algún $(p-1)$ -clan (si no fuera así podríamos añadir aristas, y entonces no sería el que tiene el mayor número de aristas posible). Llamemos $A$ a uno de esos $(p-1)$ -clanes y sea $B=V-A$ .

El grafo $A$ tiene ${p-1 \choose 2}$ aristas. Acotemos ahora el número de aristas de $B$ , $e_B$ . Por hipótesis de inducción se tiene que

$e_B \leq \cfrac{1}{2} \left ( 1- \cfrac{1}{p-1} \right ) (n-p+1)^2$

Acotemos ahora el número de aristas entre $A$ y $B$ , $e_{A,B}$ . Como $G$ no contiene $p$ -clanes, todo vértice $v_j$ de $B$ está unido con, como mucho, $p-2$ vértices de $A$ , por lo que

$e_{A,B} \leq (p-2)(n-p+1)$

Por tanto, el número de aristas de $G$ , que llamaremos $|E|$ , debe ser menor o igual que la suma de estas tres cantidades. Es decir:

$|E| \leq {p-1 \choose 2} + \cfrac{1}{2} \left ( 1- \cfrac{1}{p-1} \right ) (n-p+1)^2 + (p-2)(n-p+1)$

que, casualidades de la vida, es exactamente $\left ( 1- \cfrac{1}{p-1} \right ) \cdot \cfrac{n^2}{2}$ .

Bonita demostración, ¿verdad? Pues, como os comentaba antes, se conocen unas cuantas más. En «El Libro» aparece otra de Erdös que también usa inducción, una de Motzkin y Straus que utiliza ideas de optimización, una de Alon y Spencer que usa ideas de probabilidad y otra, cuyo origen no está claro, que utiliza una afirmación previa sobre el grafo inicial $G$ y después ideas sobre relaciones de equivalencia. Muy interesante este teorema de Turán.

Fuentes y más información: