Conde de Turana

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 9 de octubre de 2021; la verificación requiere 1 edición .

Conde de Turana

Lleva el nombre de	pal turan
picos	norte
costillas	$\left\lpiso {\frac {(r-1)n^{2}}{2r}}\right\rpiso$
Radio	$\left\{{\begin{array}{ll}\infty &r=1\\2&r\leq n/2\\1&{\text{de lo contrario}}\end{array}}\right.$
Diámetro	$\left\{{\begin{array}{ll}\infty &r=1\\1&r=n\\2&{\text{de lo contrario}}\end{array}}\right.$
Circunferencia	$\left\{{\begin{array}{ll}\infty &r=1\vee (n\leq 3\wedge r\leq 2)\\4&r=2\\3&{\text{de lo contrario)) \end{matriz}}\right.$
Número cromático	r
Designacion	= T ( norte , r )
Archivos multimedia en Wikimedia Commons

Un grafo de Turan T ( n , r ) es un grafo formado por la descomposición de n vértices en r subconjuntos, con el tamaño más cercano posible, y los vértices en este gráfico están conectados por un borde si pertenecen a diferentes subconjuntos. El gráfico tendrá subconjuntos de tamaño y subconjuntos de tamaño . Así que este es un gráfico completo de r -partitas $(n\,{\bmod {\,}}r)$ ${\ estilo de visualización \ lceil n/r \ rceil}$ $r-(n\,{\bmod {\,}}r)$ $\lpiso n/r\rpiso$

K_{\lceil n/r\rceil ,\lceil n/r\rceil ,\ldots ,\lfloor n/r\rfloor ,\lfloor n/r\rfloor }.

Cada vértice tiene grado o , o . el numero de aristas es $n-\lceil n/r\rceil$ $n-\lpiso n/r\rpiso$

{\frac {1}{2}}(n^{2}-(n\,{\bmod {\,}}r)\lceil n/r\rceil ^{2}-(r-( n\,{\bmod {\,}}r))\lpiso n/r\rpiso ^{2})\leq \left(1-{\frac {1}{r}}\right){\frac { n^{2}}{2}}.

Una gráfica es regular si n es divisible por r .

Teorema de Turan

Los grafos de Turan llevan el nombre de Pal Turan , quien los usó para probar el teorema de Turan , un resultado importante en la teoría de grafos extremos .

Por el principio de Dirichlet , cualquier conjunto de r + 1 vértices en un gráfico de Turan incluye dos vértices de la misma fracción del gráfico. Por lo tanto, el gráfico de Turan no contiene una camarilla de tamaño r + 1. De acuerdo con el teorema de Turan, el gráfico de Turan tiene el máximo número posible de aristas entre todos los gráficos sin camarillas de tamaño r + 1 que tienen n vértices. Kivash y Sudakov (Keevash y Sudakov, 2003) demostraron que el grafo de Turan es el único grafo sin camarillas de tamaño r + 1 de orden n en el que cualquier subconjunto de α n vértices tiene al menos aristas si α está lo suficientemente cerca de 1. El El teorema de Erdős-Stone amplía el teorema de Turan al limitar el número de aristas en un gráfico que no tiene un gráfico de Turan fijo como subgráfico. Como consecuencia de este teorema, en la teoría de grafos extremales, para cualquier subgrafo prohibido, se pueden probar cotas similares dependiendo del número cromático del subgrafo. ${\frac {r\,{-}\,1}{2r}}(2\alpha -1)n^{2}$

Ocasiones especiales

Algunos valores del parámetro r de los gráficos de Turan conducen a gráficos notables, que se estudian por separado.

El gráfico de Turan T (2 n , n ) se puede obtener eliminando una coincidencia perfecta del gráfico completo K 2 n . Como lo muestra Roberts ( Roberts 1969 ), el marco de este gráfico es exactamente n . Este conde se refiere a veces como el conde de Roberts . Este gráfico también es un esqueleto de 1 cógrafo de n dimensiones . Por ejemplo, la gráfica T (6,3) = K 2,2,2 es la gráfica de un octaedro regular . Si n parejas vienen a una fiesta y cada persona les da la mano a todos excepto a su pareja, entonces este gráfico describe un conjunto de apretones de manos. Por esta razón, también se le conoce como el Conde del Cóctel .

El grafo de Turan T ( n ,2) es un grafo bipartito completo , y si n es par, es un grafo de Moore . Si r es un divisor de n , el gráfico de Turan es simétrico y fuertemente regular , aunque algunos autores consideran que los gráficos de Turan son un caso trivial de regularidad fuerte y, por lo tanto, los excluyen de la definición de gráficos fuertemente regulares.

El gráfico de Turana tiene 3 a 2 b camarillas más grandes , donde 3 a + 2 b = n y b ≤ 2. Cada camarilla más grande se forma eligiendo un vértice de cada parte. Este número de camarillas más grandes es el mayor posible entre todos los gráficos con n vértices, independientemente del número de aristas en el gráfico (Moon y Moser, 1965). Estos gráficos a veces se denominan gráficos de Moon-Moser . $T(n,\lceil n/3\rceil)$

Otras propiedades

Cualquier grafo de Turan es un cografo . Por lo tanto, puede formarse a partir de vértices individuales mediante una secuencia de operaciones de unión y suma disjuntas . En particular, dicha secuencia se puede iniciar formando todos los conjuntos independientes del gráfico de Turan como una unión disjunta de vértices aislados. Entonces todo el grafo es el complemento de la unión disyuntiva de los complementos de estos conjuntos independientes.

Chao y Novacky (1982) demostraron que los gráficos de Turan son cromáticamente únicos : ningún otro gráfico tiene los mismos polinomios cromáticos . Nikiforov (Nikiforov, 2005) utilizó gráficos de Turan para encontrar el límite inferior de la suma de los k -ésimos valores propios de un gráfico y su complemento.

Falls, Powell y Snoeyink desarrollaron un algoritmo eficiente para encontrar grupos de grupos de genes ortólogos en el genoma al representar los datos como un gráfico y buscar grandes subgráficos de Turan.

Los grafos de Turan también tienen una serie de propiedades interesantes relacionadas con la teoría de grafos geométricos . Pór y Wood (2005) dan un límite inferior Ω(( rn ) 3/4 ) para cualquier incrustación de gráfico de Turan tridimensional. Witsenhausen (1974) conjeturó que la suma máxima de distancias al cuadrado entre n puntos dentro de una bola en R d de diámetro unitario se logra en la configuración formada por la incrustación del gráfico de Turan en los vértices de un símplex regular.

Un grafo G con n vértices es un subgrafo del grafo de Turan T ( n , r ) si y solo si G admite una coloración justa en r colores. La descomposición del gráfico de Turan en conjuntos independientes corresponde a la descomposición de G en clases de color. En particular, el gráfico de Turan es el único gráfico máximo de n vértices con una coloración justa en r colores.

Notas

Literatura

CY Chao, G. A. Novacky. Sobre gráficos saturados al máximo // Matemáticas discretas. - 1982. - T. 41 , núm. 2 . — S. 139–143 . - doi : 10.1016/0012-365X(82)90200-X .
Craig Falls, Bradford Powell, Jack Snoeyink. Cálculo de COG de alta rigurosidad mediante grafos tipo Turán.
Peter Keevash, Benny Sudakov. Densidad local en grafos con subgrafos prohibidos // Combinatoria, Probabilidad y Computación. - 2003. - T. 12 , núm. 2 . — S. 139–153 . -doi : 10.1017/ S0963548302005539 .
JW Luna, L. Moser. Sobre camarillas en gráficos // Israel Journal of Mathematics. - 1965. - T. 3 . — P. 23–28 . -doi : 10.1007/ BF02760024 .
Vladímir Nikiforov. Problemas de valores propios del tipo Nordhaus-Gaddum . - 2005. - arXiv : math.CO/0506260 .
Atila Por, David R Wood. proc. En t. Síntoma Dibujo gráfico (G.D. 2004) . - Apuntes de clase en informática no. 3383, Springer-Verlag, 2005, págs. 395–402. -doi : 10.1007/ b105810 .
FS Roberts. Progreso reciente en combinatoria. - Prensa Académica, 1969. - S. 301-310.
P. Turan. Sobre un problema extremo en teoría de grafos // Matematiko Fizicki Lapok. - 1941. - T. 48 . — S. 436–452 .
HS Witsenhausen. Sobre el máximo de la suma de distancias al cuadrado bajo una restricción de diámetro // American Mathematical Monthly . — The American Mathematical Monthly, vol. 81, núm. 10, 1974. - V. 81 , núm. 10 _ - S. 1100-1101 . -doi : 10.2307/ 2319046 . — .

Enlaces

Weisstein, Eric W. Cocktail Party Graph en Wolfram MathWorld .
Weisstein, Eric W. Octahedral Graph (inglés) en el sitio web de Wolfram MathWorld .
Weisstein, Eric W. Turán Gráfico (inglés) en el sitio web Wolfram MathWorld .