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 Obervació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 ..

•   Datos: Q1047749