Teorema de Erdős-Stone

Teorema de la teoría de grafos extremos

En teoría de grafos extremos , el teorema de Erdős-Stone es un resultado asintótico que generaliza el teorema de Turán para limitar el número de aristas en un gráfico libre de H para un gráfico H incompleto . Lleva el nombre de Paul Erdős y Arthur Stone , quienes lo demostraron en 1946, ^[1] y ha sido descrito como el "teorema fundamental de la teoría de grafos extremos". ^[2]

Comunicado para las gráficas de Turán

El número extremo ex ( n ;  H ) se define como el número máximo de aristas en un gráfico con n vértices que no contienen un subgrafo isomorfo a H ; consulte el problema del subgrafo prohibido para obtener más ejemplos de problemas que involucran el número extremo. El teorema de Turán dice que ex( n ;  K _r ) =  t _{r  − 1} ( n ), el número de aristas del gráfico de Turán T ( n , r − 1), y que el gráfico de Turán es el único gráfico extremo. El teorema de Erdős-Stone extiende este resultado a H  =  K _r ( t ), el gráfico r -partito completo con t vértices en cada clase, que es el gráfico obtenido tomando K _r y reemplazando cada vértice con t vértices independientes:

${\displaystyle {\mbox{ex}}(n;K_{r}(t))=\left({\frac {r-2}{r-1}}+o(1)\right){n \choose 2}.}$

Declaración para gráficos arbitrarios no bipartitos

Si H es un gráfico arbitrario cuyo número cromático es r  > 2, entonces H está contenido en K _r ( t ) siempre que t sea al menos tan grande como la clase de color más grande en una coloración r de H , pero no está contenido en el gráfico de Turán T ( n , r  − 1 ), ya que este gráfico y por tanto cada uno de sus subgrafos se pueden colorear con r  − 1 colores. De ello se deduce que el número extremo para H es al menos tan grande como el número de aristas en T ( n , r  − 1 ), y como máximo igual a la función extrema para K _r ( t ); eso es,

${\displaystyle {\mbox{ex}}(n;H)=\left({\frac {r-2}{r-1}}+o(1)\right){n \choose 2}.}$

Sin embargo, para gráficos bipartitos H , el teorema no proporciona un límite estricto para la función extrema. Se sabe que, cuando H es bipartito, ex( n ;  H ) =  o ( n ² ), y para gráficos bipartitos generales se sabe poco más. Consulte el problema de Zarankiewicz para obtener más información sobre las funciones extremas de gráficos bipartitos.

Densidad de Turán

Otra forma de describir el teorema de Erdős-Stone es utilizando la densidad de Turán de un gráfico , que está definido por . Esto determina el número extremo hasta un término de error aditivo. También se puede pensar de la siguiente manera: dada una secuencia de gráficos , cada uno de los cuales no contiene , tal que el número de vértices llega al infinito, la densidad de Turán es el límite máximo posible de sus densidades de aristas. El teorema de Erdős-Stone determina la densidad de Turán para todos los gráficos, mostrando que cualquier gráfico con número cromático tiene una densidad de Turán de ${\displaystyle H}$ ${\displaystyle \pi (H)=\lim _{n\to \infty }{\frac {{\text{ex}}(n;H)}{n \choose 2}}}$ ${\displaystyle {\text{ex(n; H)}}}$ ${\displaystyle o(n^{2})}$ ${\displaystyle G_{1},G_{2},\dots }$ ${\displaystyle H}$ ${\displaystyle H}$ ${\displaystyle r>2}$

${\displaystyle \pi (H)={\frac {r-2}{r-1}}.}$

Prueba

Una prueba del teorema de Erdős-Stone utiliza una extensión del teorema de Kővári-Sós-Turán a los hipergrafos , así como el teorema de sobresaturación , creando un hipergrafo correspondiente para cada grafo libre y mostrando que el hipergrafo tiene algún número acotado. de bordes. El Kővári-Sós-Turán dice, entre otras cosas, que el número extremo de , el gráfico bipartito completo con vértices en cada parte, es como máximo para una constante . Esto se puede extender a los hipergráficos: definiéndolo como el gráfico -partito con vértices en cada parte, luego para alguna constante . ^{[ cita necesaria ]} ${\displaystyle K_{r}(t)}$ ${\displaystyle K_{2}(t)}$ ${\displaystyle t}$ ${\displaystyle {\text{ex}}(K_{2}(t);n)\leq Cn^{2-1/t}}$ ${\displaystyle C}$ ${\displaystyle K_{s,\dots ,s}^{(r)}}$ ${\displaystyle r}$ ${\displaystyle r}$ ${\displaystyle s}$ ${\displaystyle {\text{ex}}(K_{s,\dots ,s}^{(r)},n)\leq Cn^{r-s^{1-r}}}$ ${\displaystyle C}$

Ahora, para un gráfico dado con , y algún gráfico con vértices que no contiene un subgrafo isomorfo a , definimos el gráfico con los mismos vértices que y un hiperborde entre los vértices en si forman una camarilla en . Tenga en cuenta que si contiene una copia de , entonces el gráfico original contiene una copia de , ya que cada par de vértices en partes distintas debe tener una arista. Por lo tanto, no contiene copias de y por eso tiene hiperbordes, lo que indica que hay copias de en . Por sobresaturación, esto significa que la densidad de bordes de está dentro de la densidad de Turán de , que está según el teorema de Turán ; por lo tanto, la densidad de los bordes está limitada por arriba . ${\displaystyle H=K_{r}(t)}$ ${\displaystyle r>1,s\geq 1}$ ${\displaystyle G}$ ${\displaystyle n}$ ${\displaystyle H}$ ${\displaystyle r}$ ${\displaystyle F}$ ${\displaystyle G}$ ${\displaystyle F}$ ${\displaystyle G}$ ${\displaystyle F}$ ${\displaystyle K_{s,\dots ,s}^{(r)}}$ ${\displaystyle G}$ ${\displaystyle H}$ ${\displaystyle F}$ ${\displaystyle K_{s,\dots ,s}^{(r)}}$ ${\displaystyle o(n^{r})}$ ${\displaystyle o(n^{r})}$ ${\displaystyle K_{r}}$ ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle o(1)}$ ${\displaystyle K_{r}}$ ${\displaystyle {\frac {r-2}{r-1}}}$ ${\displaystyle {\frac {r-2}{r-1}}+o(1)}$

Por otro lado, podemos lograr esta cota tomando el grafo de Turán , que no contiene copias de pero tiene aristas, mostrando que este valor es el máximo y concluyendo la prueba. ${\displaystyle T(n,r-1)}$ ${\displaystyle K_{r}(t)}$ ${\displaystyle \left({\frac {r-2}{r-1}}-o(1)\right){n \choose 2}}$

Resultados cuantitativos

Se han demostrado varias versiones del teorema que caracterizan con mayor precisión la relación de n , r , t y el término o (1) . Defina la notación ^[3] s _{r ,ε} ( n ) (para 0 < ε < 1/(2( r  − 1))) como la mayor t tal que toda gráfica de orden n y tamaño

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

contiene un K _r ( t ).

Erdős y Stone demostraron que

${\displaystyle s_{r,\varepsilon }(n)\geq \left(\underbrace {\log \cdots \log } _{r-1}\,n\right)^{1/2}}$

para n suficientemente grande. Bollobás y Erdős encontraron el orden correcto de s _{r ,ε} ( n ) en términos de n : ^[4] para cualquier r y ε dados hay constantes c ₁ ( r , ε ) y c ₂ ( r , ε ) tales que c ₁ ( r , ε ) log  n  <  s _{r ,ε} ( n ) <  c ₂ ( r , ε ) log  n . Chvátal y Szemerédi ^[5] luego determinaron la naturaleza de la dependencia de r y ε, hasta una constante:

${\displaystyle {\frac {1}{500\log(1/\varepsilon )}}\log n<s_{r,\varepsilon }(n)<{\frac {5}{\log(1/\varepsilon )}}\log n}$para n suficientemente grande  .

Notas

1. Erdős, P .; Piedra, AH (1946). "Sobre la estructura de gráficos lineales". Boletín de la Sociedad Matemática Estadounidense . 52 (12): 1087-1091. doi : 10.1090/S0002-9904-1946-08715-7 .
2. Bollobás, Béla (1998). Teoría de grafos moderna . Nueva York: Springer-Verlag . págs.120. ISBN 0-387-98491-7.
3. Bollobás, Béla (1995). "Teoría de grafos extremos". En RL Graham ; M. Grötschel ; L. Lovász (eds.). Manual de combinatoria . Elsevier . pag. 1244.ISBN​ 0-444-88002-X.
4. Bollobás, B .; Erdős, P. (1973). "Sobre la estructura de los gráficos de bordes". Boletín de la Sociedad Matemática de Londres . 5 (3): 317–321. doi :10.1112/blms/5.3.317.
5. Chvátal, V .; Szemerédi, E. (1981). "Sobre el teorema de Erdős-Stone". Revista de la Sociedad Matemática de Londres . 23 (2): 207–214. doi :10.1112/jlms/s2-23.2.207.