El grafo de Turán , denotado por , es un grafo multipartito completo ; se forma dividiendo un conjunto de vértices en subconjuntos, con tamaños lo más iguales posible, y luego conectando dos vértices por una arista si y sólo si pertenecen a subconjuntos diferentes. Donde y son el cociente y el resto de dividir por (so ), la gráfica tiene la forma y el número de aristas es
Porque , este recuento de aristas se puede expresar de forma más sucinta como . El gráfico tiene subconjuntos de tamaño y subconjuntos de tamaño ; cada vértice tiene grado o . Es un gráfico regular si es divisible por (es decir, cuando ).
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 de casillero, cada conjunto de r + 1 vértices en el gráfico de Turán incluye dos vértices en el mismo subconjunto de partición; por lo tanto, el gráfico de Turán no contiene una camarilla de tamaño r + 1. Según el teorema de Turán, el gráfico de Turán tiene el número máximo posible de aristas entre todos los gráficos sin camarilla ( r + 1) con n vértices. Keevash y Sudakov (2003) muestran que el gráfico de Turán es también el único gráfico libre de camarillas ( r + 1) de orden n en el que cada subconjunto de α n vértices abarca al menos aristas, si α está suficientemente cerca de 1. El teorema de Erdős-Stone extiende el teorema de Turán al limitar el número de aristas en un gráfico que no tiene un gráfico de Turán fijo como subgrafo. A través de este teorema, se pueden demostrar límites similares en la teoría de grafos extremos para cualquier subgrafo excluido, dependiendo del número cromático del subgrafo.
Varias elecciones del parámetro r en un gráfico de Turán conducen a gráficos notables que han sido estudiados de forma independiente.
El gráfico de Turán T (2 n , n ) se puede formar eliminando una coincidencia perfecta de un gráfico completo K 2 n . Como demostró Roberts (1969), esta gráfica tiene boxicidad exactamente n ; A veces se le conoce como gráfico de Roberts . Este gráfico es también el esqueleto unidimensional de un politopo cruzado de n dimensiones ; por ejemplo, la gráfica T (6,3) = K 2,2,2 es la gráfica octaédrica , la gráfica del octaedro regular . Si n parejas van a una fiesta y cada persona le da la mano a todos excepto a su pareja, entonces este gráfico describe el conjunto de apretones de manos que tienen lugar; por este motivo también se le llama gráfico del cóctel .
El gráfico de Turán T ( n ,2) es un gráfico bipartito completo y, cuando n es par, un gráfico de Moore . Cuando r es 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 fuerte regularidad y por tanto los excluyen de la definición de grafo fuertemente regular.
La clase de gráficos de Turán puede tener exponencialmente muchas camarillas máximas, lo que significa que esta clase no tiene pocas camarillas . Por ejemplo, el gráfico de Turán 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 gráficos de n -vértices, independientemente del número de aristas del gráfico (Moon y Moser 1965); Estas gráficas a veces se denominan gráficas de Luna-Moser .
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 y complemento disjuntas . Específicamente, tal secuencia puede comenzar formando cada uno de los conjuntos independientes del grafo de Turán como una unión disjunta de vértices aislados. Entonces, la gráfica general es el complemento de la unión disjunta de los complementos de estos conjuntos independientes.
Chao y Novacky (1982) muestran que las gráficas de Turán son cromáticamente únicas : ninguna otra gráfica tiene los mismos polinomios cromáticos . Nikiforov (2005) utiliza gráficos de Turán para proporcionar un límite inferior para la suma de los k -ésimos valores propios de un gráfico y su complemento.
Falls, Powell y Snoeyink desarrollan un algoritmo eficiente para encontrar grupos de grupos ortólogos de genes en datos del genoma, representando los datos como un gráfico y buscando grandes subgrafos de Turán.
Los grafos de Turán también tienen algunas propiedades interesantes relacionadas con la teoría de grafos geométricos . Pór y Wood (2005) dan un límite inferior de Ω(( rn ) 3/4 ) en el volumen de cualquier cuadrícula tridimensional incrustada en el gráfico de Turán. 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 incrustando un gráfico de Turán en los vértices de un simplex regular.
Un gráfico de n -vértices G es un subgrafo de un gráfico de Turán T ( n , r ) si y sólo si G admite una coloración equitativa con r colores. La partición del gráfico de Turán en conjuntos independientes corresponde a la partición de G en clases de color. En particular, el gráfico de Turán es el único gráfico de n -vértices máximo con una coloración equitativa de r -color.
