Gráfica de Turán

Gráfico multipartito completo balanceado

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 posibles, y luego conectando dos vértices por una arista si y solo si pertenecen a subconjuntos diferentes. Donde y son el cociente y el resto de dividir por (por lo que ), el grafo tiene la forma , y el número de aristas es ${\displaystyle T(n,r)}$ ${\displaystyle n}$ ${\displaystyle r}$ ${\displaystyle q}$ ${\displaystyle s}$ ${\displaystyle n}$ ${\displaystyle r}$ ${\displaystyle n=qr+s}$ ${\displaystyle K_{q+1,q+1,\ldots ,q,q}}$

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

Para , 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 ). ${\displaystyle r\leq 7}$ ${\displaystyle \left\lfloor \left(1-{\frac {1}{r}}\right){\frac {n^{2}}{2}}\right\rfloor }$ ${\displaystyle s}$ ${\displaystyle q+1}$ ${\displaystyle r-s}$ ${\displaystyle q}$ ${\displaystyle n-q-1}$ ${\displaystyle n-q}$ ${\displaystyle n}$ ${\displaystyle r}$ ${\displaystyle s=0}$

Teorema de Turán

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 .

Por 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 máximo número 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 aristas, si α es suficientemente cercano a 1. ^[1] El teorema de Erdős-Stone extiende el teorema de Turán al limitar 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 límites similares en la teoría de grafos extremos para cualquier subgrafo excluido, dependiendo del número cromático del subgrafo. ${\displaystyle {\frac {r\,{-}\,1}{3r}}(2\alpha -1)n^{2}}$

Casos especiales

El octaedro , un politopo de 3 cruces cuyas aristas y vértices forman K _2,2,2 , un grafo de Turán T (6,3). Los vértices no conexos reciben el mismo color en esta proyección centrada en las caras.

Varias elecciones del parámetro r en un gráfico de Turán conducen a gráficos notables que han sido estudiados independientemente.

El grafo de Turán T (2 n , n ) se puede formar eliminando una coincidencia perfecta de un grafo completo K _{2 n} . Como Roberts (1969) mostró, este grafo tiene boxicidad exactamente n ; a veces se lo conoce como el grafo de Roberts . ^{[2] Este grafo también es el} esqueleto 1 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 estrecha 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 lo llama grafo 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 divisor de n , el grafo de Turán es simétrico y fuertemente regular , aunque algunos autores consideran a los grafos de Turán como un caso trivial de fuerte regularidad y por tanto los excluyen de la definición de 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 tiene 3 ^a 2 ^b cliques máximos , donde 3 a  + 2 b  =  n y b  ≤ 2; cada clique máximo se forma eligiendo un vértice de cada subconjunto de partición. Este es el mayor número de cliques máximos 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] ${\displaystyle T(n,\lceil n/3\rceil )}$

Otras propiedades

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 . En concreto, 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. Entonces, el grafo global 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 un límite inferior para la suma de los k -ésimos valores propios 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 del genoma, representando los datos como un gráfico y buscando grandes subgrafos de Turán. ^[5]

Los grafos de Turán también tienen algunas propiedades interesantes relacionadas con la teoría geométrica de grafos . Pór y Wood (2005) dan un límite inferior de Ω(( rn ) ^{3/4 ) en el volumen de cualquier} incrustación en una 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 símplex regular. ^[7]

Un grafo de n vértices G 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 de n vértices maximal con una coloración equitativa con r colores.

Notas

1. Keevash y Sudakov (2003).
2. Roberts (1969).
3. Luna y Moser (1965).
4. Chao y Novacky (1982).
5. Caídas, Powell y Snoeyink (2003).
6. Por y Wood (2005).
7. Vitsenhausen (1974).

Referencias

• Chao, CY; Novacky, GA (1982). "Sobre grafos máximamente saturados". Matemáticas discretas . 41 (2): 139–143. doi : 10.1016/0012-365X(82)90200-X .
• Falls, Craig; Powell, Bradford; Snoeyink, Jack (2003). "Cálculo de COG de alta rigurosidad utilizando grafos de tipo Turán" (PDF) .
• Keevash, Peter; Sudakov, Benny (2003). "Densidad local en grafos con subgrafos prohibidos" (PDF) . Combinatoria, probabilidad y computación . 12 (2): 139–153. doi :10.1017/S0963548302005539. S2CID  17854032.
• Moon, JW; Moser, L. (1965). "Sobre camarillas en grafos". Revista israelí de matemáticas . 3 : 23–28. doi :10.1007/BF02760024. S2CID  9855414.
• Nikiforov, Vladimir (2007). "Problemas de valores propios del tipo Nordhaus-Gaddum". Matemáticas discretas . 307 (6): 774–780. arXiv : math.CO/0506260 . doi : 10.1016/j.disc.2006.07.035 .
• Pór, Attila; Wood, David R. (2005). "No-three-in-line-in-3D". Proc. Int. Symp. Graph Drawing (GD 2004) . Apuntes de clase en Ciencias de la Computación n.º 3383, Springer-Verlag. págs. 395–402. doi :10.1007/b105810. hdl : 11693/27422 .
• Roberts, FS (1969). Tutte, WT (ed.). "Sobre la boxicidad y la cubicidad de un grafo". Recent Progress in Combinatorics : 301–310.
• Turán, P. (1941). "Egy gráfelméleti szélsőértékfeladatról (Sobre un problema extremo en teoría de grafos)". Matematikai és Fizikai Lapok . 48 : 436–452.
• Witsenhausen, HS (1974). "Sobre el máximo de la suma de distancias al cuadrado bajo una restricción de diámetro". American Mathematical Monthly . 81 (10): 1100–1101. doi :10.2307/2319046. JSTOR  2319046.

Enlaces externos

• Weisstein, Eric W. "Gráfico de cóctel". MundoMatemático .
• Weisstein, Eric W. "Gráfico octaédrico". MathWorld .
• Weisstein, Eric W. "Gráfico de Turán". MundoMatemático .