Teorema de Turán

Esta era la prueba original de Turán. Toma una${\displaystyle K_{r+1}}$-gráfico gratuito en${\displaystyle n}$vértices con el número máximo de aristas. Encuentra un${\displaystyle K_{r}}$(que existe por maximalidad), y particionamos los vértices en el conjunto${\displaystyle A}$del${\displaystyle r}$vértices en el${\displaystyle K_{r}}$y el conjunto${\displaystyle B}$del${\displaystyle nr}$otros vértices.

Ahora bien, se pueden delimitar los bordes anteriores de la siguiente manera:

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

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

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

Ahora, elimine todos los bordes dentro${\displaystyle A}$y dibujar todos los bordes entre${\displaystyle A}$y${\displaystyle B}$Esto aumenta el número de aristas según nuestra suposición de maximalidad y mantiene el grafo.${\displaystyle K_{r+1}}$-gratis. Ahora,${\displaystyle B}$es${\displaystyle K_{r}}$-libre, por lo que el mismo argumento puede repetirse en${\displaystyle B}$.

Al repetir este argumento, se obtiene un grafo con la misma forma que un grafo de Turán , que es una colección de conjuntos independientes, con aristas entre cada par de vértices de diferentes conjuntos independientes. Un cálculo sencillo muestra que el número de aristas de este grafo se maximiza cuando los tamaños de todos los conjuntos independientes son lo más parecidos posible. ^{[ 3 ] [ 4 ]}

Esta demostración, al igual que la demostración de simetrización de Zykov, implica reducir al caso en que el grafo es un grafo multipartito completo y demostrar que el número de aristas se maximiza cuando hay${\displaystyle r}$conjuntos independientes de tamaño lo más parecido posible. Este paso se puede realizar de la siguiente manera:

Dejar${\displaystyle S_{1},S_{2},\ldots ,S_{r}}$sean los conjuntos independientes del grafo multipartito. Dado que 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 \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 deriva del conteo directo y el lado derecho se deriva del conteo complementario. Para mostrar el${\displaystyle \left(1-{\frac {1}{r}}\right){\frac {n^{2}}{2}}}$límite, aplicando la desigualdad de Cauchy-Schwarz a la${\textstyle \sum \limits _{i}\left|S_{i}\right|^{2}}$El término del lado derecho es suficiente, ya que${\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${\displaystyle S_{i}}$difieren en más de uno en tamaño. En particular, suponiendo que tenemos${\displaystyle \left|S_{i}\right|\geq \left|S_{j}\right|+2}$para algunos${\displaystyle i\neq j}$, moviendo un vértice desde${\displaystyle S_{i}}$a${\displaystyle S_{j}}$(y ajustando las aristas en consecuencia) aumentaría el valor de la suma. Esto se puede observar al examinar los cambios en ambos lados de la expresión anterior para el número de aristas, o al notar que el grado del vértice movido aumenta.

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

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

Ahora bien, la desigualdad de Cauchy-Schwarz establece que el valor máximo es como máximo ${\displaystyle {\frac {1}{2}}\left(1-{\frac {1}{r}}\right)}$. Conectando${\displaystyle x_{i}={\frac {1}{n}}}$a pesar de${\displaystyle i}$indica que el valor máximo es al menos${\displaystyle {\frac {|E|}{n^{2}}}}$, dando el límite deseado. ^{[ 3 ] [ 5 ]}

La afirmación clave en esta demostración fue hallada independientemente por Caro y Wei. Esta demostración se debe a Noga Alon y Joel Spencer , de su libro El método probabilístico . La demostración muestra que todo grafo con grados${\displaystyle d_{1},d_{2},\ldots ,d_{n}}$tiene un conjunto independiente de tamaño al menos$${\displaystyle S={\frac {1}{d_{1}+1}}+{\frac {1}{d_{2}+1}}+\cdots +{\frac {1}{d_{n}+1}}.}$$La demostración intenta encontrar un conjunto independiente de la siguiente manera:

• Consideremos una permutación aleatoria de los vértices de un${\displaystyle K_{r+1}}$-gráfico gratuito
• Seleccione todos los vértices que no sean adyacentes a ninguno de los vértices anteriores.

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

Aplicando este hecho al grafo complementario y acotando el tamaño del conjunto elegido mediante 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.

Aigner y Ziegler llaman a la última de sus cinco demostraciones "la más bella de todas". Sus orígenes no están claros, pero el enfoque a menudo se denomina 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 consiste en tomar una${\displaystyle K_{r+1}}$-grafo libre, y aplicando pasos para hacerlo más similar al grafo de Turán mientras se aumenta el número de aristas.

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

• Si${\displaystyle u,v}$son vértices no adyacentes y${\displaystyle u}$tiene un grado más alto que${\displaystyle v}$, reemplazar${\displaystyle v}$con una copia de${\displaystyle u}$Repita este proceso hasta que todos los vértices no adyacentes tengan el mismo grado.
• Si${\displaystyle u,v,w}$son vértices con${\displaystyle u,v}$y${\displaystyle v,w}$no adyacentes pero${\displaystyle u,w}$adyacentes, luego reemplace ambos${\displaystyle u}$y${\displaystyle w}$con copias de${\displaystyle v}$.

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

Ahora bien, la no adyacencia forma una relación de equivalencia . Las clases de equivalencia hacen que cualquier grafo maximal tenga la misma forma que un grafo de Turán. Como en la demostración del grado máximo del vértice, un cálculo sencillo muestra que el número de aristas se maximiza cuando todos los tamaños de conjuntos independientes son lo más parecidos posible. ^{[ 3 ]}

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

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

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

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

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

(Teorema de Zykov) El gráfico en${\displaystyle n}$vértices sin${\displaystyle K_{r+1}}$s y el mayor número posible de${\displaystyle K_{a}}$s es el gráfico de Turán${\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${\displaystyle r}$piezas con un tamaño aproximado${\displaystyle {\frac {n}{r}}}$, el número de${\displaystyle K_{a}}$s en${\displaystyle T(n,r)}$está alrededor${\displaystyle {\binom {r}{a}}\left({\frac {n}{r}}\right)^{a}}$Un artículo de Alon y Shikhelman de 2016 ofrece la siguiente generalización, que es similar a la generalización de Erdos-Stone del teorema de Turán:

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

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

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

Un problema al responder esta pregunta es que, para una densidad dada, puede existir un límite que ningún grafo alcanza, pero al que se aproxima una secuencia infinita de grafos. Para abordar esto, se suelen considerar los grafos ponderados o grafones . En particular, los grafones contienen el límite de cualquier secuencia infinita de grafos.

Para una densidad de borde dada${\displaystyle d}$, la construcción para el más grande${\displaystyle K_{r}}$La densidad es la siguiente:

Tomar varios vértices${\displaystyle N}$acercándose al infinito. Elija un conjunto de${\displaystyle {\sqrt {d}}N}$de los vértices, y conectar dos vértices si y solo si están en el conjunto elegido.

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

Consideremos un número de vértices que tiende al infinito. Sea${\displaystyle t}$sea ​​el número entero tal que${\displaystyle 1-{\frac {1}{t-1}}<d\leq 1-{\frac {1}{t}}}$. Toma un${\displaystyle t}$-grafo partito 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 tal manera que la densidad total de aristas sea${\displaystyle d}$.

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

La cota inferior fue demostrada por Razborov (2008) ^{[ 10 ]} para el caso de triángulos, y posteriormente fue generalizada a todas las camarillas por Reiher (2016) ^{[ 11 ]} . La cota superior es una consecuencia del teorema de Kruskal-Katona ^{[ 12 ]} .