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 ${\displaystyle K_{r+1}}$-clanes.

Un grafo con ${\displaystyle n}$ vértices que no contiene ningún ${\displaystyle (r+1)}$-clan puede ser formado de una partición del conjunto de vértices en ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle n}$ vértices que son libres de ${\displaystyle 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 ${\displaystyle G}$ un grafo en ${\displaystyle n}$ vértices, tal que ${\displaystyle G}$ es ${\displaystyle K_{r+1}}$-libre. Entonces, el número de aristas en G es a lo sumo

${\displaystyle {\frac {r-1}{r}}\cdot {\frac {n^{2}}{2}}=\left(1-{\frac {1}{r}}\right)\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 ${\displaystyle (r+1)}$-clanes, ${\displaystyle T(n,r)}$ tiene el máximo número de aristas posible.

Prueba

Sea ${\displaystyle G}$ un grafo simple en ${\displaystyle n}$ vértices que no contiene ${\displaystyle (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 ${\displaystyle (r+1)}$-clanes y con máximo número de ejes posibles tiene que ser un grafo de Turán. Por ejemplo, cuando ${\displaystyle 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 ${\displaystyle A}$ y ${\displaystyle B}$ , donde ${\displaystyle |A|=12}$ y ${\displaystyle |B|=11}$. Colocamos una arista entre cualquier par vértices tales que uno está en ${\displaystyle A}$ y el otro está en ${\displaystyle B}$ pero no si ambos están en ${\displaystyle A}$ o en ${\displaystyle B}$. Por lo tanto, el número total de aristas es

${\displaystyle 11\cdot 12=132\leq {\frac {23^{2}}{2}}\left(1-{\frac {1}{2}}\right)=132.25}$

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

Definimos la siguiente relación entre los vértices de ${\displaystyle G}$:

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

Para demostrar esta observación, es suficiente demostrar que ${\displaystyle \sim }$ es una relación de equivalencia, ya que esto implicaría que está relación particiona los vértices de ${\displaystyle G}$ en ${\displaystyle k}$ clases de equivalencia ${\displaystyle S_{1},\ldots ,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 ${\displaystyle k}$-clan, implicando que ${\displaystyle k<r+1}$. La relación es reflexiva, ya que ${\displaystyle 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 ${\displaystyle u,v,w}$ en la gráfica tales que ${\displaystyle u\sim v}$ y ${\displaystyle v\sim w}$, pero ${\displaystyle u\not \sim w}$. Si denotamos ${\displaystyle d(x)}$ por el grado de un vértice ${\displaystyle x}$, nos encontramos en uno de los siguientes casos:

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

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

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

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

Caso 2: ${\displaystyle d(v)\geq d(u)}$ y ${\displaystyle d(v)\geq d(w)}$

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

${\displaystyle |E(G')|=|E(G)|-(d(u)+d(w)-1)+2d(v)\geq |E(G)|+1.}$

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

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

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

Gracias a las Observaciones 1 y 2, la única posibilidad restante de que dicho grafo ${\displaystyle G}$ maximal no sea un grafo de Turán es que tenga menos de ${\displaystyle r}$ partes. Sin embargo, en dicho caso podemos también tratar a ${\displaystyle G}$ como un grafo ${\displaystyle 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 ${\displaystyle \lfloor n^{2}/4\rfloor .}$ (Mantel, 1907)

En otras palabras, para obtener un grafo libre de triángulos a partir del grafo completo ${\displaystyle 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 ${\displaystyle n^{2}/4}$ aristas tiene que ser el grafo completo bipartita ${\displaystyle 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 ${\displaystyle 1,2,\cdots ,V(G)}$ (Bondy 1971).

Otra versión fuerte del teorema de Mantel establece que para cualquier grafo en ${\displaystyle n}$ vértices, este puede ser cubierto por una colección de a lo sumo ${\displaystyle \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 ${\displaystyle \lfloor n^{2}/4\rfloor }$ (Erdős, Goodman y Pósa, 1966).

Referencias

• Aigner, Martin; Ziegler, Günter M. (1998), Proofs from THE BOOK, Berlín, New York: Springer-Verlag ..
• Bondy, J. Un. (1971), "Pancyclic graphs I", Bondy, J. A. (1971), «Pancyclic graphs I», Journal of Combinatorial Theory, Series B 11 (1): 80-84, doi:10.1016/0095-8956(71)90016-5 ..
• 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.
• Mantel, W. (1907), «Problem 28 (Solution by H. Gouwentak, W. Mantel, J. Teixeira de Mattes, F. Schuh and W. A. Wythoff)», Wiskundige Opgaven 10: 60-61 .
• Turán, Paul (1941), «On an extremal problem in graph theory», Matematikai és Fizikai Lapok (en hungarian) 48: 436-452. .
• West, Douglas Brent (1999) [1996], Introduction to Graph Theory (2nd edición), Prentice Hall, ISBN 978-0-13-014400-3 ..