Grafo de Turán

subconjuntos, con tamaños lo más iguales posibles, y conectando dos vértices por una esquina sí y solo sí estos pertenecen a subconjuntos diferentes.-partito completo Cada vértice tiene grados o deEl número de esquinas es Se convierte en un grafo regular cuandoLos grafos de Turán deben su nombre Pál Turán, quien los utilizó para probar el teorema de Turán, un importante resultado en la teoría de grafos extremales.vértices en el grafo de Turán incluyen dos vértices en el mismo subconjunto de partición; por lo tanto, el grafo de Turán no contiene un clique de tamañoKeevash y Sudakov, en 2003, demostraron que el grafo de Turán es el único grafo libre de cliquevértices se extiende al menosestá lo suficientemente cerca de 1.A través de este teorema, límites similares en la teoría de grafos extremales puede ser probada para cada subgrafo excluido, dependiendo en el número cromático del subgrafo.Varias opciones del parámetroen un grafo de Turán dirigen a notables grafos que han sido estudiados independientemente.puede ser formado removiendo el emparejamiento perfecto de un grafo completoComo mostró Roberts en 1969, este grafo tiene una boxicidad de exactamente; es a veces conocido como el grafo de Roberts.[3]​ Este grafo es también el 1-esqueleto de un ortoplexparejas van a una fiesta, y cada persona se aprieta de manos con cada persona a excepción de su pareja, entonces este grafo describe el conjunto de apretones de manos que tomaron lugar; por esta razón es también llamado el grafo de veladas (del inglés cocktail party graph).es un grafo bipartito completo y, cuandoes par, un grafo de Moore., el grafo de Turán es simétrico y fuertemente regular, a pesar de que algunos autores consideran a los grafos de Turán ser un caso trivial de fuerte regularidad y por lo tanto los excluyen de la definición de un grafo fuertemente regular.Este es el número más grande de cliqués posibles entre todos los grafos de[4]​ Cada grafo de Turán es un cografo; es decir que puede ser formado a partir de vértices individuales por una secuencia de operaciones de uniones disjuntas y grafos complemento.Chao y Novacky mostraron en 1982 que los grafos de Turán son cromáticamente únicos: ningún otro grafo tiene los mismos polinomios cromáticos.[5]​ Nikiforov en 2005 utilizó los grafos de Turán para suplementar un límite menor para la suma del-ésimo eigenvector de un grafo y su complemento.[6]​ Falls, Powell, y Snoeyink desarrollaron un algoritmo eficiente para encontrar racimos de grupos de genes ortólogos en los datos del genoma, representando los datos como un grafo y buscando grandes subgrafos de Turán.[7]​ Los grafos de Turán también tienen propiedades interesantes relacionadas con la teoría de grafos geométricos.Pór y Wood en 2005 dieron un límite menor de[8]​ Witsenhausen en 1974 conjetura que la suma máxima de distancias al cuadrado, entrees alcanzado por una configuración formada al incrustar un grafo de Turán en los vértices de un símplex regular.La partición del grafo de Turán en conjuntos independientes corresponde a la partición de