Teorema de Turán

En teoría de grafos, El teorema de Turán es un resultado sobre en número de aristas en un grafo libre de $K_{r+1}$-clanes.

Un grafo con $n$ vértices que no contiene ningún $(r+1)$-clan puede ser formado de una partición del conjunto de vértices en $r$ partes de igual tamaño (o cuyo tamaño difiere en a lo más en un vértice), y conectando cualesquiera dos vértices pertenecientes a partes distintas. El grafo resultante es el grafo de Turán $T(n,r)$. El teorema de Turán establece que el grafo de Turán es aquel con el mayor número de aristas posible entre todos los grafos con $n$ vértices que son libres de $K_{r+1}$-clanes.

Los grafos de Turán fueron descubiertos y estudiados por el matemático húngaro Pál Turán en 1941; sin embargo, un caso especial de dicho teorema fue demostrado anteriormente por Mantel en 1907.

Enunciado del Teorema

Teorema de Turán. Sea $G$ un grafo en $n$ vértices, tal que $G$ es $K_{r+1}$-libre. Entonces, el número de aristas en G es a lo sumo

$\frac{r-1}{r}\cdot \frac{n^2}{2}=(1-\frac{1}{r})\cdot \frac{n^2}{2}.$

Una formulación equivalente es la siguiente:

Teorema de Turán (segunda formulación) De entre todos los grafos simples que son libres de $(r+1)$-clanes, $T(n,r)$ tiene el máximo número de aristas posible.

Prueba

Sea $G$ un grafo simple en $n$ vértices que no contiene $(r+1)$-clanes y que contiene el máximo número de aristas posibles.

Idea general Demostramos que un grafo en n vértices libre de $(r+1)$-clanes y con máximo número de ejes posibles tiene que ser un grafo de Turán. Por ejemplo, cuando $n=23$, para formar un grafo libre de triángulos, o 3-cliques, que maximiza el número de aristas, comenzamos por subdividir el conjunto de vértices en dos grupos $A$ y $B$ , donde $|A|=12$ y $|B|=11$. Colocamos una arista entre cualquier par vértices tales que uno está en $A$ y el otro está en $B$ pero no si ambos están en $A$ o en $B$. Por lo tanto, el número total de aristas es

$11\cdot 12=132\le \frac{23^2}{2}(1-\frac{1}{2})=132.25$

Observación 1: $G$ es un grafo completo $k$-bipartita, para algún $k<r+1$

Definimos la siguiente relación entre los vértices de $G$:

$x\sim y$ sí y sólo si $x$ no está conectado a $y$

Para demostrar esta observación, es suficiente demostrar que $\sim$ es una relación de equivalencia, ya que esto implicaría que está relación particiona los vértices de $G$ en $k$ clases de equivalencia $S_1,\dots ,S_k$ tales que ningún par de vértices dentro de la misma clase están conectados, y cualesquiera dos vértices en clases diferentes están conectados. Más aún, el subgrafo que se obtendría de escoger un vértice de cada clase de equivalencia formaría un $k$-clan, implicando que $k<r+1$. La relación es reflexiva, ya que $G$ es una gráfica simple y ningún vértice está conectado consigo mismo. Además, es claramente simétrica, por lo que sólo queda por demostrar la propiedad de transitividad.

Con el fin de llegar a una contradicción, supongamos que dicha relación no es transitiva. Entonces, hay tres vértices $u,v,w$ en la gráfica tales que $u\sim v$ y $v\sim w$, pero $u\sim ̸w$. Si denotamos $d(x)$ por el grado de un vértice $x$, nos encontramos en uno de los siguientes casos:

Caso 1: $d(v)<d(u)\text{ o }d(v)<d(w)$

Sin pérdida de generalidad, $d(v)<d(u)$. Removemos al vértice $v$ y creamos una copia del vértice $u$ (que tenga los mismos vértices adyacentes que $u$), al que llamaremos $u^{\prime }$. Llamemos a esta nueva gráfica $G^{\prime }$. Ya que $u\sim ̸u^{\prime }$, la mayor clique en $G^{\prime }$ no puede tener más vértices que la mayor clique en $G$. Sin embargo, $G^{\prime }$ contiene más ejes ya que:

$|E(G^{\prime })|=|E(G)|-d(v)+d(u)>|E(G)|.$

lo cual contradice la maximalidad del número de aristas en $G$ como grafo $K_{r+1}$-libre.

Caso 2: $d(v)\ge d(u)$ y $d(v)\ge d(w)$

En este caso, removemos los vértices $u$ y $w$ y creamos dos copias del vértice $v$. Como en el caso 1, tenemos una contradicción, pues el grafo $G^{\prime }$ que se obtiene de este proceso no puede contener $(r+1)$-clanes, pero tiene más aristas:

$|E(G^{\prime })|=|E(G)|-(d(u)+d(w)-1)+2d(v)\ge |E(G)|+1.$

Ya que en cualquiera de los dos casos arriba, $G^{\prime }$ contiene más aristas que $G$, obtenemos una contradicción, por lo que $\sim$ es transitiva, y concluimos que es una relación de equivalencia.

Observación 2: El número de aristas en una gráfica $k$-partita completa es maximizado cuando cualesquiera dos de las partes en que el conjunto de vértices queda subdividido difieren en tamaño en a lo más 1.

Si $G$ fuera una gráfica completa $k$-partita, con partes $A$ y $B$ tales que $|A|>|B|+1$, entonces podemos aumentar el número de aristas en $G$ trasladando un vértice de la parte $A$ a la parte $B$, y actualizando sus vértices vecinos. Al hacer esto, el grafo pierde $|B|$ aristas, pero obtiene $|A|-1$. Entonces, en total el número de aristas aumentó ya que $|A|-1-|B|\ge 1$. Con esto demostramos la segunda observación.

Observación 3: $G$ tiene que ser un grafo de Turán.

Gracias a las Observaciones 1 y 2, la única posibilidad restante de que dicho grafo $G$ maximal no sea un grafo de Turán es que tenga menos de $r$ partes. Sin embargo, en dicho caso podemos también tratar a $G$ como un grafo $r$-partita con algunas de sus partes vacías, i.e. conteniendo 0 vértices, y aplicar el mismo razonamiento de la Observación 2.

Teorema de Mantel

Este teorema es un caso especial del Teorema de Turán , cuando r = 2. Explícitamente, este es su enunciado:

Teorema de Mantel. El número máximo de aristas en un grafo libre de triángulos es $\lfloor n^2/4\rfloor .$ (Mantel, 1907)

En otras palabras, para obtener un grafo libre de triángulos a partir del grafo completo $K_n$, se deben de eliminar esencialmente la mitad de las aristas.

Una versión más fuerte del Teorema de Mantel establece que cualquier grafo Hamiltoniano con al menos $n^2/4$ aristas tiene que ser el grafo completo bipartita $K_{n/2,n/2}$, o de lo contrario es pancíclico; no solo contiene un triángulo, sino que además contiene ciclos de todas las posibles longitudes $1,2,\cdots ,V(G)$ (Bondy 1971).

Otra versión fuerte del teorema de Mantel establece que para cualquier grafo en $n$ vértices, este puede ser cubierto por una colección de a lo sumo $\lfloor n^2/4\rfloor$ clanes de tamaño 2 o 3. Un corolario de este resultado es que el número de intersecciones es a lo sumo $\lfloor n^2/4\rfloor$ Plantilla:Cita Harvard.

Referencias

• Plantilla:Obra citada.
• Bondy, J. Un. (1971), "Pancyclic graphs I", Plantilla:Obra citada.
• Erdős, Paul; Goodman, Un. W.; Pósa, Louis (1966), "The representation of a graph by self intersections" (PDF), Canadian Journal of Mathematics, 18 (1): 106@–112, doi:10.4153/CJM-1966-014-3, SEÑOR 0186575.
• Plantilla:Citation
• Plantilla:Citation
• Plantilla:Obra citada.