Gráfico de Turán

El gráfico de Turán , denotado por${\displaystyle T(n,r)}$, es un grafo multipartito completo ; se forma mediante la partición de un conjunto de${\displaystyle n}$vértices en${\displaystyle r}$subconjuntos, con tamaños lo más iguales posible, y luego conectar dos vértices por una arista si y solo si pertenecen a subconjuntos diferentes.${\displaystyle q}$y${\displaystyle s}$son el cociente y el resto de la división${\displaystyle n}$por${\displaystyle r}$(entonces${\displaystyle n=qr+s}$), el gráfico tiene la forma${\displaystyle K_{q+1,q+1,\ldots ,q,q}}$y el número de aristas es

${\displaystyle \left(1-{\frac {1}{r}}\right){\frac {n^{2}-s^{2}}{2}}+{s \choose 2}}$.

Para${\displaystyle r\leq 7}$, este recuento de aristas se puede expresar de forma más concisa como${\displaystyle \left\lfloor \left(1-{\frac {1}{r}}\right){\frac {n^{2}}{2}}\right\rfloor }$. El gráfico tiene${\displaystyle s}$subconjuntos de tamaño${\displaystyle q+1}$, y${\displaystyle rs}$subconjuntos de tamaño${\displaystyle q}$; cada vértice tiene grado${\displaystyle nq-1}$o${\displaystyle nq}$. Es un gráfico regular si${\displaystyle n}$es divisible por${\displaystyle r}$(es decir cuando${\displaystyle s=0}$).

Los grafos de Turán llevan el nombre de Pál Turán , quien los usó para demostrar el teorema de Turán , un resultado importante en la teoría de grafos extremos .

Según el principio del palomar, cada conjunto de r  +  1 vértices en el grafo de Turán incluye dos vértices en el mismo subconjunto de partición; por lo tanto, el grafo de Turán no contiene una camarilla de tamaño r + 1. Según el teorema de Turán, el grafo de Turán tiene el número máximo posible de aristas entre todos los grafos libres de camarillas ( r + 1) con n vértices. Keevash y Sudakov (2003) muestran que el grafo de Turán es también el único grafo libre de camarillas ( r + 1) de orden n en el que cada subconjunto de α n vértices abarca al menos        ${\displaystyle {\frac {r\,{-}\,1}{3r}}(2\alpha -1)n^{2}}$bordes, si α está suficientemente cerca de 1. ^{[ 1 ]} El teorema de Erdős-Stone extiende el teorema de Turán al acotar el número de aristas en un grafo que no tiene un grafo de Turán fijo como subgrafo. Mediante este teorema, se pueden demostrar cotas similares en la teoría extremal de grafos para cualquier subgrafo excluido, dependiendo del número cromático del subgrafo.

En un gráfico de Turán , diversas elecciones del parámetro r dan lugar a gráficos notables que han sido estudiados de forma independiente.

El grafo de Turán T (2 n , n ) se puede formar eliminando un emparejamiento perfecto de un grafo completo K _{2 n} . Como mostró Roberts (1969) , este grafo tiene boxicidad exactamente n ; a veces se le conoce como el grafo de Roberts . ^{[ 2 ]} Este grafo es también el 1- esqueleto de un politopo cruzado n -dimensional ; por ejemplo, el grafo T (6,3) = K _2,2,2 es el grafo octaédrico , el grafo del octaedro regular . Si n parejas van a una fiesta, y cada persona da la mano a todas las personas excepto a su pareja, entonces este grafo describe el conjunto de apretones de manos que tienen lugar; por esta razón, también se le llama el grafo de la fiesta de cóctel .  

El grafo de Turán T ( n ,2) es un grafo bipartito completo y, cuando n es par, un grafo de Moore . Cuando r es un divisor de n , el grafo de Turán es simétrico y fuertemente regular , aunque algunos autores consideran que los grafos de Turán son un caso trivial de regularidad fuerte y, por lo tanto, los excluyen de la definición de un grafo fuertemente regular.

La clase de grafos de Turán puede tener exponencialmente muchos cliques máximos, lo que significa que esta clase no tiene pocos cliques . Por ejemplo, el grafo de Turán${\displaystyle T(n,\lceil n/3\rceil )}$tiene 3 ^a 2 ^b camarillas máximas , donde 3 a  +  2 b  = n y b ≤ 2; cada camarilla máxima se forma eligiendo un vértice de cada subconjunto de partición. Este es el mayor número de camarillas máximas posible entre todos los grafos de n vértices, independientemente del número de aristas en el grafo; estos grafos a veces se denominan grafos de Moon-Moser . ^{[ 3 ]}   

Todo grafo de Turán es un cografo ; es decir, puede formarse a partir de vértices individuales mediante una secuencia de operaciones de unión disjunta y complemento . Específicamente, dicha secuencia puede comenzar formando cada uno de los conjuntos independientes del grafo de Turán como una unión disjunta de vértices aislados. Luego, el grafo resultante es el complemento de la unión disjunta de los complementos de estos conjuntos independientes.

Chao y Novacky (1982) demuestran que los grafos de Turán son cromáticamente únicos : ningún otro grafo tiene los mismos polinomios cromáticos . Nikiforov (2005) utiliza los grafos de Turán para proporcionar una cota inferior para la suma de los k -ésimos autovalores de un grafo y su complemento. ^{[ 4 ]}

Falls, Powell y Snoeyink (2003) desarrollan un algoritmo eficiente para encontrar grupos de genes ortólogos en datos genómicos, representando los datos como un grafo y buscando subgrafos de Turán grandes. ^{[ 5 ]}

Los grafos de Turán también poseen algunas propiedades interesantes relacionadas con la teoría geométrica de grafos . Pór y Wood (2005) proporcionan una cota inferior de Ω(( rn ) ^{3/4 ) para el volumen de cualquier} incrustación de cuadrícula tridimensional del grafo de Turán. ^{[ 6 ]} Witsenhausen (1974) conjetura que la suma máxima de distancias al cuadrado, entre n puntos con diámetro unitario en R ^d , se alcanza para una configuración formada al incrustar un grafo de Turán en los vértices de un simplex regular. ^{[ 7 ]}

Un grafo G de n vértices es un subgrafo de un grafo de Turán T ( n , r ) si y solo si G admite una coloración equitativa con r colores. La partición del grafo de Turán en conjuntos independientes corresponde a la partición de G en clases de color. En particular, el grafo de Turán es el único grafo maximal de n vértices con una coloración equitativa de r colores.

• Weisstein, Eric W. "Gráfico de cóctel" . MundoMatemático .
• Weisstein, Eric W. "Grafo octaédrico" . MathWorld .
• Weisstein, Eric W. "Gráfico de Turán" . MundoMatemático .
• Datos de diseño de cobertura : base de datos de hipergrafos extremales y diseños de cobertura mantenida por Klas Markström.