Teorema de Turán

Teoría de grafos extremos limitada por aristas de grafos libres de camarillas

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 extremales , un área que estudia los grafos más grandes o más pequeños con propiedades dadas, y es un caso especial del problema del subgrafo prohibido sobre el número máximo de aristas en un grafo que no tiene un subgrafo dado.

Un ejemplo de un grafo de vértices que no contiene ninguna camarilla de vértices se puede formar dividiendo el conjunto de vértices en partes de tamaño igual o casi igual, y conectando dos vértices por una arista siempre que pertenezcan a dos partes diferentes. El grafo resultante es el grafo de Turán . El teorema de Turán establece que el grafo de Turán tiene el mayor número de aristas entre todos los grafos de n vértices libres de K _{r +1} . ${\displaystyle n}$ ${\displaystyle (r+1)}$ ${\displaystyle K_{r+1}}$ ${\displaystyle n}$ ${\displaystyle r}$ ${\displaystyle T(n,r)}$

El teorema de Turán, y los grafos 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 para grafos sin triángulos se conoce como teorema de Mantel ; fue enunciado en 1907 por Willem Mantel, un matemático holandés. ^[2]

Declaración

El teorema de Turán establece que todo grafo con vértices que no contenga como subgrafo tiene como máximo tantas aristas como el grafo de Turán . Para un valor fijo de , este grafo tiene aristas, utilizando la notación o minúscula . Intuitivamente, esto significa que a medida que se hace más grande, la fracción de aristas incluidas en se acerca cada vez más a . Muchas de las siguientes demostraciones solo dan el límite superior de . ^[3] ${\displaystyle G}$ ${\displaystyle n}$ ${\displaystyle K_{r+1}}$ ${\displaystyle T(n,r)}$ ${\displaystyle r}$ $${\displaystyle \left(1-{\frac {1}{r}}+o(1)\right){\frac {n^{2}}{2}}}$$ ${\displaystyle n}$ ${\displaystyle T(n,r)}$ ${\displaystyle 1-{\frac {1}{r}}}$ ${\displaystyle \left(1-{\frac {1}{r}}\right){\frac {n^{2}}{2}}}$

Pruebas

Aigner y Ziegler (2018) enumeran cinco pruebas diferentes del teorema de Turán. ^[3] Muchas de las pruebas implican la reducción al caso en el que el gráfico es un gráfico multipartito completo y muestran que el número de aristas se maximiza cuando hay partes de tamaño lo más cercano posible al igual. ${\displaystyle r}$

Inducción

(Inducción sobre n) Un ejemplo de conjuntos y para . ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle r=3}$

(Vértice de grado máximo) Eliminar aristas dentro y dibujar aristas entre y . ${\displaystyle A}$ ${\displaystyle A}$ ${\displaystyle B}$

Esta fue la demostración original de Turán. Tómese un grafo libre de vértices con el número máximo de aristas. Encuentre un (que existe por maximalidad) y divida los vértices en el conjunto de los vértices en el y el conjunto de los otros vértices. ${\displaystyle K_{r+1}}$ ${\displaystyle n}$ ${\displaystyle K_{r}}$ ${\displaystyle A}$ ${\displaystyle r}$ ${\displaystyle K_{r}}$ ${\displaystyle B}$ ${\displaystyle n-r}$

Ahora, uno puede limitar los bordes superiores de la siguiente manera:

• Hay exactamente bordes dentro de . ${\displaystyle {\binom {r}{2}}}$ ${\displaystyle A}$
• Hay como máximo aristas entre y , ya que ningún vértice en puede conectarse a todos los . ${\displaystyle (r-1)|B|=(r-1)(n-r)}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle B}$ ${\displaystyle A}$
• El número de aristas dentro es como máximo el número de aristas de según la hipótesis inductiva. ${\displaystyle B}$ ${\displaystyle T(n-r,r)}$

Sumando estos límites se obtiene el resultado. ^{[1] [3]}

Vértice de grado máximo

Esta demostración se debe a Paul Erdős . Tome el vértice de mayor grado. Considere el conjunto de vértices no adyacentes a y el conjunto de vértices adyacentes a . ${\displaystyle v}$ ${\displaystyle A}$ ${\displaystyle v}$ ${\displaystyle B}$ ${\displaystyle v}$

Ahora, elimine todas las aristas dentro de y dibuje todas las aristas entre y . Esto aumenta la cantidad de aristas según nuestro supuesto de maximalidad y mantiene el gráfico libre de . Ahora, es libre de , por lo que el mismo argumento se puede repetir en . ${\displaystyle A}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle K_{r+1}}$ ${\displaystyle B}$ ${\displaystyle K_{r}}$ ${\displaystyle B}$

La repetición de este argumento produce eventualmente un grafo con la misma forma que un grafo de Turán , que es una colección de conjuntos independientes, con aristas entre cada dos vértices de diferentes conjuntos independientes. Un cálculo simple muestra que la cantidad de aristas de este grafo se maximiza cuando todos los tamaños de conjuntos independientes son lo más cercanos a la igualdad posible. ^{[3] [4]}

Optimización multipartita completa

Esta prueba, así como la prueba de simetrización de Zykov, implican la reducción al caso en el que el grafo es un grafo multipartito completo y la demostración de que el número de aristas se maximiza cuando hay conjuntos independientes de tamaño lo más cercano posible al mismo. Este paso se puede realizar de la siguiente manera: ${\displaystyle r}$

Sean los conjuntos independientes del grafo multipartito. Como dos vértices tienen una arista entre ellos si y solo si no están en el mismo conjunto independiente, el número de aristas es ${\displaystyle S_{1},S_{2},\ldots ,S_{r}}$

$${\displaystyle \sum _{i\neq j}\left|S_{i}\right|\left|S_{j}\right|={\frac {1}{2}}\left(n^{2}-\sum _{i}\left|S_{i}\right|^{2}\right),}$$

donde el lado izquierdo se sigue del conteo directo, y el lado derecho se sigue del conteo complementario. Para mostrar el límite, basta con aplicar la desigualdad de Cauchy-Schwarz al término del lado derecho, ya que . ${\displaystyle \left(1-{\frac {1}{r}}\right){\frac {n^{2}}{2}}}$ ${\textstyle \sum \limits _{i}\left|S_{i}\right|^{2}}$ ${\textstyle \sum \limits _{i}\left|S_{i}\right|=n}$

Para demostrar que el grafo de Turán es óptimo, se puede argumentar que no hay dos que difieran en más de uno en tamaño. En particular, suponiendo que tenemos para algún , mover un vértice de a (y ajustar las aristas en consecuencia) aumentaría el valor de la suma. Esto se puede ver examinando los cambios a ambos lados de la expresión anterior para el número de aristas, o notando que el grado del vértice movido aumenta. ${\displaystyle S_{i}}$ ${\displaystyle \left|S_{i}\right|\geq \left|S_{j}\right|+2}$ ${\displaystyle i\neq j}$ ${\displaystyle S_{j}}$ ${\displaystyle S_{i}}$

Lagrangiano

Esta prueba se debe a Motzkin y Straus (1965). Comienzan considerando un grafo libre con vértices etiquetados como , y consideran maximizar la función sobre todos los no negativos con suma . Esta función se conoce como el lagrangiano del grafo y sus aristas. ${\displaystyle K_{r+1}}$ ${\displaystyle 1,2,\ldots ,n}$ $${\displaystyle f(x_{1},x_{2},\ldots ,x_{n})=\sum _{i,j\ {\text{adjacent}}}x_{i}x_{j}}$$ ${\displaystyle x_{1},x_{2},\ldots ,x_{n}}$ ${\displaystyle 1}$

La idea detrás de su demostración es que si ambos son distintos de cero mientras que no son adyacentes en el gráfico, la función es lineal en . Por lo tanto, uno puede reemplazar con cualquiera de ellos o sin disminuir el valor de la función. Por lo tanto, hay un punto con como máximo variables distintas de cero donde la función se maximiza. ${\displaystyle x_{i},x_{j}}$ ${\displaystyle i,j}$ $${\displaystyle f(x_{1},\ldots ,x_{i}-t,\ldots ,x_{j}+t,\ldots ,x_{n})}$$ ${\displaystyle t}$ ${\displaystyle (x_{i},x_{j})}$ ${\displaystyle (x_{i}+x_{j},0)}$ ${\displaystyle (0,x_{i}+x_{j})}$ ${\displaystyle r}$

Ahora bien, la desigualdad de Cauchy-Schwarz indica que el valor máximo es como máximo . Si se sustituyen todos los valores, se obtiene que el valor máximo es al menos , lo que da el límite deseado. ^{[3] [5]} ${\displaystyle {\frac {1}{2}}\left(1-{\frac {1}{r}}\right)}$ ${\displaystyle x_{i}={\frac {1}{n}}}$ ${\displaystyle i}$ ${\displaystyle {\frac {|E|}{n^{2}}}}$

Método probabilístico

La afirmación clave de esta prueba fue encontrada independientemente por Caro y Wei. Esta prueba se debe a Noga Alon y Joel Spencer , de su libro The Probabilistic Method . La prueba muestra que cada grafo con grados tiene un conjunto independiente de tamaño al menos. La prueba intenta encontrar dicho conjunto independiente de la siguiente manera: ${\displaystyle d_{1},d_{2},\ldots ,d_{n}}$ $${\displaystyle S={\frac {1}{d_{1}+1}}+{\frac {1}{d_{2}+1}}+\cdots +{\frac {1}{d_{n}+1}}.}$$

• Considere una permutación aleatoria de los vértices de un gráfico libre de ${\displaystyle K_{r+1}}$
• Seleccione cada vértice que no sea adyacente a ninguno de los vértices anteriores.

Se incluye un vértice de grado con probabilidad , por lo que este proceso da un promedio de vértices en el conjunto elegido. ${\displaystyle d}$ ${\displaystyle {\frac {1}{d+1}}}$ ${\displaystyle S}$

(Simetrización de Zykov) Ejemplo del primer paso.

Aplicando este hecho al gráfico del complemento y acotando el tamaño del conjunto elegido utilizando la desigualdad de Cauchy-Schwarz se demuestra el teorema de Turán. ^[3] Véase Método de probabilidades condicionales § Teorema de Turán para más información.

(Simetrización de Zykov) Ejemplo de segundo paso.

Simetrización de Zykov

Aigner y Ziegler llaman a la última de sus cinco demostraciones "la más hermosa de todas". Sus orígenes no están claros, pero el enfoque se conoce a menudo como simetrización de Zykov, ya que se utilizó en la demostración de Zykov de una generalización del teorema de Turán ^[6] . Esta demostración se basa en tomar un grafo libre y aplicar pasos para hacerlo más similar al grafo de Turán mientras se aumenta el número de aristas. ${\displaystyle K_{r+1}}$

En particular, dado un gráfico libre, se aplican los siguientes pasos: ${\displaystyle K_{r+1}}$

• Si son vértices no adyacentes y tiene un grado mayor que , reemplácelo con una copia de . Repita esto hasta que todos los vértices no adyacentes tengan el mismo grado. ${\displaystyle u,v}$ ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle v}$ ${\displaystyle u}$
• Si los vértices con y no son adyacentes pero sí adyacentes, entonces reemplace ambos y con copias de . ${\displaystyle u,v,w}$ ${\displaystyle u,v}$ ${\displaystyle v,w}$ ${\displaystyle u,w}$ ${\displaystyle u}$ ${\displaystyle w}$ ${\displaystyle v}$

Todos estos pasos mantienen el gráfico libre mientras aumentan el número de aristas. ${\displaystyle K_{r+1}}$

Ahora bien, la no adyacencia forma una relación de equivalencia . Las clases de equivalencia dan a cualquier grafo maximalista la misma forma que un grafo de Turán. Como en la prueba de vértice de grado máximo, 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 cercanos a la igualdad 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 grafo sin triángulos en -vértice es ^[2] En otras palabras, uno debe eliminar casi la mitad de las aristas en para obtener un grafo sin triángulos. ${\displaystyle r=2}$ ${\displaystyle n}$ ${\displaystyle \lfloor n^{2}/4\rfloor .}$ ${\displaystyle K_{n}}$

Una forma reforzada del teorema de Mantel establece que cualquier grafo hamiltoniano con al menos aristas debe ser un grafo bipartito completo o debe ser pancíclico : no solo contiene un triángulo, sino que también debe contener ciclos de todas las demás longitudes posibles hasta el número de vértices del grafo. ^[7] ${\displaystyle n^{2}/4}$ ${\displaystyle K_{n/2,n/2}}$

Otro refuerzo del teorema de Mantel establece que las aristas de cada grafo de vértice pueden estar cubiertas, como máximo, por camarillas que sean aristas o triángulos. Como corolario, el número de intersección del grafo (el número mínimo de camarillas necesarias para cubrir todas sus aristas) es, como máximo , . ^[8] ${\displaystyle n}$ ${\displaystyle \lfloor n^{2}/4\rfloor }$ ${\displaystyle \lfloor n^{2}/4\rfloor }$

Generalizaciones

Otros subgrafos prohibidos

El teorema de Turán muestra que el mayor número de aristas en un grafo libre es . El teorema de Erdős-Stone halla el número de aristas hasta un error en todos los demás grafos: ${\displaystyle K_{r+1}}$ ${\displaystyle \left(1-{\frac {1}{r}}+o(1)\right){\frac {n^{2}}{2}}}$ ${\displaystyle o(n^{2})}$

(Erdős–Stone) Supongamos que es un grafo con número cromático . El mayor número posible de aristas en un grafo donde no aparece como subgrafo es donde la constante solo depende de . ${\displaystyle H}$ ${\displaystyle \chi (H)}$ ${\displaystyle H}$ $${\displaystyle \left(1-{\frac {1}{\chi (H)-1}}+o(1)\right){\frac {n^{2}}{2}}}$$ ${\displaystyle o(1)}$ ${\displaystyle H}$

Se puede observar que el gráfico de Turán no puede contener ninguna copia de , por lo que el gráfico de Turán establece el límite inferior. Como a tiene número cromático , el teorema de Turán es el caso especial en el que es a . ${\displaystyle T(n,\chi (H)-1)}$ ${\displaystyle H}$ ${\displaystyle K_{r+1}}$ ${\displaystyle r+1}$ ${\displaystyle H}$ ${\displaystyle K_{r+1}}$

La pregunta general de cuántas aristas se pueden incluir en un gráfico sin una copia de alguna es el problema del subgráfico prohibido . ${\displaystyle H}$

Maximizar otras cantidades

Otra extensión natural del teorema de Turán es la siguiente pregunta: si un grafo no tiene s, ¿cuántas copias de puede tener? El teorema de Turán es el caso donde . El teorema de Zykov responde a esta pregunta: ${\displaystyle K_{r+1}}$ ${\displaystyle K_{a}}$ ${\displaystyle a=2}$

(Teorema de Zykov) El grafo sobre vértices sin s y con el mayor número posible de s es el grafo de Turán ${\displaystyle n}$ ${\displaystyle K_{r+1}}$ ${\displaystyle K_{a}}$ ${\displaystyle T(n,r)}$

Esto fue demostrado por primera vez por Zykov (1949) utilizando la simetrización de Zykov ^{[1] [3]} . Dado que el grafo de Turán contiene partes con un tamaño de alrededor de , el número de s en es de alrededor de . Un artículo de Alon y Shikhelman en 2016 ofrece la siguiente generalización, que es similar a la generalización de Erdos-Stone del teorema de Turán: ${\displaystyle r}$ ${\displaystyle {\frac {n}{r}}}$ ${\displaystyle K_{a}}$ ${\displaystyle T(n,r)}$ ${\displaystyle {\binom {r}{a}}\left({\frac {n}{r}}\right)^{a}}$

(Alon-Shikhelman, 2016) Sea un grafo con número cromático . El mayor número posible de s en un grafo sin copia de es ^[9] ${\displaystyle H}$ ${\displaystyle \chi (H)>a}$ ${\displaystyle K_{a}}$ ${\displaystyle H}$ ${\displaystyle (1+o(1)){\binom {\chi (H)-1}{a}}\left({\frac {n}{\chi (H)-1}}\right)^{a}.}$

Al igual que en Erdős–Stone, el gráfico de Turán alcanza el número deseado de copias de . ${\displaystyle T(n,\chi (H)-1)}$ ${\displaystyle K_{a}}$

Región Edge-Clique

El teorema de Turan establece que si un grafo tiene una densidad de homomorfismo de aristas estrictamente superior a , tiene un número de s distinto de cero. Se podría plantear una pregunta mucho más general: si se nos da la densidad de aristas de un grafo, ¿qué podemos decir sobre la densidad de s? ${\displaystyle 1-{\frac {1}{r-1}}}$ ${\displaystyle K_{r}}$ ${\displaystyle K_{r}}$

Un problema que surge al responder a esta pregunta es que, para una densidad dada, puede haber algún límite que no se alcance con ningún grafo, pero que se alcance con una secuencia infinita de grafos. Para abordar este problema, a menudo se consideran los grafos ponderados o grafones . En particular, los grafones contienen el límite de cualquier secuencia infinita de grafos.

Para una densidad de aristas dada , la construcción para la mayor densidad es la siguiente: ${\displaystyle d}$ ${\displaystyle K_{r}}$

Tome una cantidad de vértices que se acerquen al infinito. Elija un conjunto de vértices y conecte dos vértices si y solo si están en el conjunto elegido. ${\displaystyle N}$ ${\displaystyle {\sqrt {d}}N}$

Esto da una densidad de La construcción para la densidad más pequeña es la siguiente: ${\displaystyle K_{r}}$ ${\displaystyle d^{k/2}.}$ ${\displaystyle K_{r}}$

Consideremos una cantidad de vértices que se acerque al infinito. Sea el entero tal que . Consideremos un grafo de -particiones donde todas las partes excepto la parte más pequeña tienen el mismo tamaño, y los tamaños de las partes se eligen de manera que la densidad total de aristas sea . ${\displaystyle t}$ ${\displaystyle 1-{\frac {1}{t-1}}<d\leq 1-{\frac {1}{t}}}$ ${\displaystyle t}$ ${\displaystyle d}$

Para , esto da un gráfico que es -partito y, por lo tanto, no da s. ${\displaystyle d\leq 1-{\frac {1}{r-1}}}$ ${\displaystyle (r-1)}$ ${\displaystyle K_{r}}$

El límite inferior fue demostrado por Razborov (2008) ^[10] para el caso de triángulos, y luego fue generalizado a todas las camarillas por Reiher (2016) ^[11] . El límite superior es una consecuencia del teorema de Kruskal-Katona ^[12] .

Véase también

• Teorema de Erdős-Stone , una generalización del teorema de Turán desde camarillas prohibidas hasta gráficos prohibidos de Turán

Referencias

1. Turán, Paul (1941), "Sobre un problema extremo en teoría de grafos", Matematikai és Fizikai Lapok (en húngaro), 48 : 436–452
2. 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
3. Aigner, Martin ; Ziegler, Günter M. (2018), "Capítulo 41: Teorema de grafos de Turán", Demostraciones del LIBRO (6.ª ed.), Springer-Verlag, págs. 285–289, doi :10.1007/978-3-662-57265-8_41, ISBN 978-3-662-57265-8
4. Erdős, Pál (1970), "Turán Pál gráf tételéről" [Sobre el teorema del grafo de Turán] (PDF) , Matematikai Lapok (en húngaro), 21 : 249–251, MR  0307975
5. Motzkin, TS ; Straus, EG (1965), "Máximos para grafos y una nueva prueba de un teorema de Turán", Revista Canadiense de Matemáticas , 17 : 533–540, doi : 10.4153/CJM-1965-053-6 , MR  0175813, S2CID  121387797
6. Zykov, A. (1949), "Sobre algunas propiedades de los complejos lineales", Mat. Sb. , Nueva serie (en ruso), 24 : 163–188
7. 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
8. Erdős, Paul ; Goodman, AW ; Pósa, Louis (1966), "La representación de un gráfico por intersecciones de conjuntos" (PDF) , Revista canadiense de matemáticas , 18 (1): 106–112, doi :10.4153/CJM-1966-014-3, MR  0186575, S2CID  646660
9. Alon, Noga; Shikhelman, Clara (2016), "Muchas copias T en gráficos libres de H", Journal of Combinatorial Theory, Serie B , 121 : 146–172, arXiv : 1409.4192 , doi : 10.1016/j.jctb.2016.03.004 , S2CID  5552776
10. Razborov, Alexander (2008). "Sobre la densidad mínima de triángulos en grafos" (PDF) . Combinatoria, probabilidad y computación . 17 (4): 603–618. doi :10.1017/S0963548308009085. S2CID  26524353 – vía MathSciNet (AMS).
11. Reiher, Christian (2016), "El teorema de densidad de camarillas", Anales de Matemáticas , 184 (3): 683–707, arXiv : 1212.2454 , doi :10.4007/annals.2016.184.3.1, S2CID  59321123
12. Lovász, László, Grandes redes y límites de gráficos