En teoría de grafos , el teorema de Turán limita el número de aristas que se pueden incluir en un grafo no dirigido que no tiene un subgrafo completo de un tamaño dado. Es uno de los resultados centrales de la teoría de grafos extremos , un área que estudia los gráficos más grandes o más pequeños con propiedades dadas, y es un caso especial del problema de subgrafo prohibido en el número máximo de aristas en un gráfico que no tiene un subgrafo dado. .
Un ejemplo de - gráfico de vértice que no contiene ningúncamarilla del vértice puede formarse dividiendo el conjunto de vértices en partes de igual o casi igual tamaño, y conectando dos vértices por un borde siempre que pertenezcan a dos partes diferentes. El gráfico resultante es el gráfico de Turán . Teorema de Turan que la gráfica Turán tiene el mayor número de aristas entre todos los K r +1 -free n gráficos -vertex.
El teorema de Turán, y los gráficos de Turán que dan su caso extremo, fueron descritos y estudiados por primera vez por el matemático húngaro Pál Turán en 1941. [1] El caso especial del teorema de los gráficos sin triángulos se conoce como teorema de Mantel ; fue declarado en 1907 por Willem Mantel, un matemático holandés. [2]
Declaración
El teorema de Turán establece que toda gráfica con vértices que no contiene como un subgrafo tiene un número de bordes que es como máximo
La misma fórmula da el número de aristas en el gráfico de Turán , por lo que equivale a enunciar el teorema de Turán en la forma que, entre los -Gráficos simples de vértice sin -cliques, tiene el número máximo de aristas. [3]
Pruebas
Aigner y Ziegler (2018) enumeran cinco pruebas diferentes del teorema de Turán. [3]
La demostración original de Turán usa la inducción sobre el número de vértices. Dado un-vértice -Gráfico gratuito con más de vértices y un número máximo de aristas, la prueba encuentra una camarilla (que debe existir por maximalidad), lo elimina y aplica la inducción al resto -Subgrafo de vértice. Cada vértice del subgrafo restante puede ser adyacente como máximo vértices de camarilla, y sumando el número de aristas obtenidas de esta forma con el número inductivo de aristas en el -El subgrafo de vértice da el resultado. [1] [3]
Una prueba diferente de Paul Erdős encuentra el vértice de grado máximo a partir de una -free gráfico y lo usa para construir un nuevo gráfico en el mismo conjunto de vértices eliminando los bordes entre cualquier par de no vecinos de y agregar bordes entre todos los pares de un vecino y un no vecino. El nuevo gráfico permanece-free y tiene al menos la misma cantidad de bordes. Repetir la misma construcción de forma recursiva en el subgrafo de vecinos de eventualmente produce un gráfico en la misma forma que un gráfico de Turán (una colección de conjuntos independientes, con aristas entre cada dos vértices de diferentes conjuntos independientes) y un cálculo simple muestra que el número de aristas de este gráfico se maximiza cuando todos los tamaños de conjuntos independientes son lo más iguales posible. [3] [4]
Motzkin y Straus (1965) prueban el teorema de Turán utilizando el método probabilístico , buscando una distribución de probabilidad discreta en los vértices de una determinada-Gráfico libre que maximiza el número esperado de aristas en un subgrafo inducido elegido al azar , con cada vértice incluido en el subgrafo de forma independiente con la probabilidad dada. Para una distribución con probabilidad para el vértice , este número esperado es . Cualquier distribución de este tipo puede modificarse, cambiando repetidamente la probabilidad entre pares de vértices no adyacentes, de modo que el valor esperado no disminuya y los únicos vértices con probabilidad distinta de cero pertenezcan a una camarilla, de lo cual se deduce que el valor máximo esperado está en la mayoría. Por lo tanto, el valor esperado para la distribución uniforme, que es exactamente el número de aristas dividido por, es también como máximo , y el número de aristas en sí es como máximo . [3] [5]
Una demostración de Noga Alon y Joel Spencer , de su libro The Probabilistic Method , considera una permutación aleatoria de los vértices de un-Gráfico libre, y la camarilla más grande formada por un prefijo de esta permutación. Calculando la probabilidad de que se incluya cualquier vértice dado, en función de su grado, se puede demostrar que el tamaño esperado de esta camarilla es, dónde es el grado de vértice . Debe existir una camarilla de al menos este tamaño, por lo que. Cierta manipulación algebraica de esta desigualdad utilizando la desigualdad de Cauchy-Schwarz y el lema del apretón de manos demuestra el resultado. [3] Ver Método de probabilidades condicionales § Teorema de Turán para más información.
Aigner y Ziegler llaman a la última de sus cinco pruebas "la más hermosa de todas"; sus orígenes no están claros. Se basa en un lema que, para una máxima-Gráfico libre, la no adyacencia es una relación transitiva , porque si por el contrario y eran no adyacentes y eran adyacentes se podía construir un -Gráfico libre con más aristas eliminando uno o dos de estos tres vértices y reemplazándolos por copias de uno de los vértices restantes. Debido a que la no adyacencia también es simétrica y reflexiva (ningún vértice es adyacente a sí mismo), forma una relación de equivalencia cuyas clases de equivalencia dan a cualquier gráfico máximo la misma forma que un gráfico de Turán. Como en la segunda prueba, un cálculo simple muestra que el número de aristas se maximiza cuando todos los tamaños de conjuntos independientes son lo más iguales posible. [3]
Teorema de mantel
El caso especial del teorema de Turán para es el teorema de Mantel: el número máximo de aristas en un -El gráfico sin triángulos de vértice es[2] En otras palabras, se debe eliminar casi la mitad de los bordes en para obtener un gráfico sin triángulos.
Una forma reforzada del teorema de Mantel establece que cualquier grafo hamiltoniano con al menos los bordes deben ser el gráfico bipartito completo o debe ser pancíclico : no solo contiene un triángulo, también debe contener ciclos de todas las demás longitudes posibles hasta el número de vértices del gráfico. [6]
Otro fortalecimiento del teorema de Mantel establece que los bordes de cada -El gráfico de vértice puede estar cubierto por como máximo camarillas que son bordes o triángulos. Como corolario, el número de intersección del gráfico (el número mínimo de grupos necesarios para cubrir todos sus bordes) es como máximo. [7]
Ver también
- Teorema de Erdős-Stone , una generalización del teorema de Turán de camarillas prohibidas a grafos de Turán prohibidos
Referencias
- ↑ a b Turán, Paul (1941), "Sobre un problema extremo en la teoría de grafos", Matematikai és Fizikai Lapok (en húngaro), 48 : 436–452
- ^ a b Mantel, W. (1907), "Problema 28 (Solución de H. Gouwentak, W. Mantel, J. Teixeira de Mattes, F. Schuh y WA Wythoff)", Wiskundige Opgaven , 10 : 60-61
- ^ a b c d e f g Aigner, Martin ; Ziegler, Günter M. (2018), "Capítulo 41: Teorema del gráfico de Turán", Proofs from THE BOOK (6th ed.), Springer-Verlag, pp. 285-289, doi : 10.1007 / 978-3-662-57265- 8_41 , ISBN 978-3-662-57265-8
- ^ Erdős, Pál (1970), "Turán Pál gráf tételéről" [Sobre el teorema de grafos de Turán] (PDF) , Matematikai Lapok (en húngaro), 21 : 249-251, MR 0307975
- ^ Motzkin, TS ; Straus, EG (1965), "Máximos para gráficas y una nueva demostración de un teorema de Turán", Canadian Journal of Mathematics , 17 : 533–540, doi : 10.4153 / CJM-1965-053-6 , MR 0175813
- ^ Bondy, JA (1971), "Gráficos pancíclicos I", Journal of Combinatorial Theory , Serie B , 11 (1): 80-84, doi : 10.1016 / 0095-8956 (71) 90016-5
- ^ Erdős, Paul ; Goodman, AW ; Pósa, Louis (1966), "La representación de un gráfico por intersecciones de conjuntos" (PDF) , Canadian Journal of Mathematics , 18 (1): 106–112, doi : 10.4153 / CJM-1966-014-3 , MR 0186575