Grafo de Turán

De Wikipedia, la enciclopedia libre

El grafo de Turán
Nombre en honor a Pál Turán
Vértices
Aristas
Radio
Diámetro
Cintura
Número cromático
Notación

El grafo de Turán es un grafo multipartito completo formado por el posicionamiento de un conjunto de vértices dentro de 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. El grafo tendrá conjuntos de tamaño, y subconjuntos de tamaño. Es decir, un grafo -partito completo

Cada vértice tiene grados o de o de . El número de esquinas es

Se convierte en un grafo regular cuando es divisible por .

Teorema de Turán[editar]

Los 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.[1]

Por el principio de Dirichlet, cada conjunto de 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ño . De acuerdo al teorema de Turán, el grafo de Turán tiene el máximo número posible de esquinas entre todo grafo libre de clique con vértices. Keevash y Sudakov, en 2003, demostraron que el grafo de Turán es el único grafo libre de clique de orden , en el cual cada subconjunto de vértices se extiende al menos esquinas, si está lo suficientemente cerca de 1.[2]​ El teorema de Erdős–Stone extiende al teorema de Turán limitando el número de aristas en un grafo que no tiene un grafo de Turán arreglado como un subgrafo. 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.

Casos especiales[editar]

El octaedro es un 3-ortoplex cuyas aristas y vértices forman , un grafo de Turán . Los vértices no conectados están dados en el mismo color en esta proyección centrada en la cara.

Varias opciones del parámetro en un grafo de Turán dirigen a notables grafos que han sido estudiados independientemente.

El grafo de Turán puede ser formado removiendo el emparejamiento perfecto de un grafo completo . Como 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 ortoplex -dimensional; por ejemplo, el grafo es el grafo octahédrico, el grafo de un octaedro regular. Si parejas 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).

El grafo de Turán es un grafo bipartito completo y, cuando es par, un grafo de Moore. Cuando es divisor de , 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.

El grafo de Turán tiene cliqués máximos, donde y ; cada clique máximo es formado eligiendo un vértice de cada subconjunto de partición. Este es el número más grande de cliqués posibles entre todos los grafos de -vértices independientemente del número de aristas en el grafo; estos grafos son varias veces llamados grafos de Moon–Moser.[4]

Otras propiedades[editar]

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. Específicamente, tal secuencia puede iniciar formando cada uno de los conjuntos independientes de los grafos de Turán como una unión disjunta de vértices aislados. Entonces, el grafo total es el complemento de la unión disjunta de los complementos de esos conjuntos independientes.

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 en el volumen de cualquier rejilla tridimensional del grafo de Turán.[8]​ Witsenhausen en 1974 conjetura que la suma máxima de distancias al cuadrado, entre puntos con diámetro unitario en es alcanzado por una configuración formada al incrustar un grafo de Turán en los vértices de un símplex regular.[9]

Un grafo de -vértices es el subgrafo de un grafo de Turán sí y solo sí admite una coloración equitativa con colores. La partición del grafo de Turán en conjuntos independientes corresponde a la partición de en clases de color. En particular, el grafo de Turán es el único grafo de -vértices máximos con una coloración equitativa .

Referencias[editar]

  1. Turán, P. (1941). «Egy gráfelméleti szélsőértékfeladatról» [Sobre un problema extremal en teoría de grafos]. Matematikai és Fizikai Lapok (en húngaro) 48: 436-452. 
  2. Keevash, Benny; Sudakov (2003). «Local density in graphs with forbidden subgraphs». Combinatorics, Probability and Computing (en inglés) (Cambridge University Press) 12 (2): 139-153. ISSN 0963-5483. doi:10.1017/S0963548302005539. 
  3. Roberts, F. S. (1969). «On the boxicity and cubicity of a graph». En Tutte, W. T., ed. Recent Progress in Combinatorics (en inglés) (Academic Press): 301-310. 
  4. Moon, J. W.; Moser, L. (1965). «On cliques in graphs». Israel Journal of Mathematics (en hebreo e inglés) (Magnes Press) 3: 23-28. ISSN 0021-2172. doi:10.1007/BF02760024. 
  5. Chao, C. Y.; Novacky, G. A. (1982). «On maximally saturated graphs». Discrete Mathematics (en inglés) (Elsevier) 41 (2): 139-143. ISSN 0012-365X. doi:10.1016/0012-365X(82)90200-X. 
  6. Nikiforov, Vladimir (2005). Eigenvalue problems of Nordhaus-Gaddum type (en inglés). arXiv:math.CO/0506260. 
  7. Falls, Craig; Powell, Bradford; Snoeyink, Jack. Computing high-stringency COGs using Turán type graphs (PDF) (en inglés). 
  8. Pór, Attila; Wood, David R. (2005). No-three-in-line-in-3D. «Proc. Int. Symp. Graph Drawing (GD 2004)». Lecture Notes in Computer Science 3383 (Springer): 395-402. doi:10.1007/b105810. 
  9. Witsenhausen, H. S. (1974). «On the maximum of the sum of squared distances under a diameter constraint». American Mathematical Monthly (en inglés) (American Mathematical Society) 81 (10): 1100-1101. ISSN 0002-9890. JSTOR 2319046. doi:10.2307/2319046. 

Enlaces externos[editar]