Gráfico de Turán
El grafo Turán T ( n , r ) es un grafo multipartito completo formado al dividir un conjunto de n vértices en r subconjuntos, con tamaños lo más iguales posible, y conectando dos vértices por una arista si y solo si pertenecen a diferentes subconjuntos. Donde con , el gráfico tendrá subconjuntos de tamaño y subconjuntos de tamaño . Es decir, es un grafo de partita r completo . Cada vértice tiene un grado o . El número de aristas es
Los gráficos de Turán llevan el nombre de Pál Turán , quien los utilizó para probar el teorema de Turán , un resultado importante en la teoría de grafos extremos .
Por el principio de casillero, cada conjunto de vértices r + 1 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 un clique 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 libres de clique ( 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 clicas ( r + 1) de orden n en el que cada subconjunto de α n vértices abarca al menos aristas, si α está lo suficientemente cerca de 1. La Teorema de Erdős-Stoneextiende el teorema de Turán acotando el número de aristas en un gráfico que no tiene un gráfico de Turán fijo como subgráfico. A través de este teorema, se pueden probar 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 se han estudiado 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 mostró Roberts (1969) , este gráfico tiene una boxicidad exactamente n ; a veces se lo conoce como el gráfico de Roberts . Este gráfico es también el 1- esqueleto de un n -dimensional politopo de cruce ; por ejemplo, el gráfico T (6,3) = K 2,2,2 es el gráfico octaédrico , el gráfico del octaedro regular . Sin las parejas van a una fiesta y cada persona le da la mano a todas las personas excepto a su pareja, luego este gráfico describe el conjunto de apretones de manos que se llevan a cabo; por esta razón también se le llama gráfico de 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 un divisor de n , el gráfico de Turán es simétrico y fuertemente regular , aunque algunos autores consideran que los gráficos de Turán son un caso trivial de fuerte regularidad y, por lo tanto, los excluyen de la definición de un gráfico fuertemente regular.
