Teorema de Erdös-Stone

Teorema en la teoría de grafos extremos

En la teoría de grafos extremales , 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 grafo libre de H para un grafo no completo H. Recibe su nombre en honor a 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 extremales”. ^[2]

Declaración sobre los gráficos de Turán

El número extremal ex( n ;  H ) se define como el número máximo de aristas en un grafo con n vértices que no contiene un subgrafo isomorfo a H ; véase el Problema del subgrafo prohibido para más ejemplos de problemas que involucran el número extremal. El teorema de Turán dice que ex( n ;  K _r ) =  t _{r  − 1} ( n ), el número de aristas del grafo de Turán T ( n , r − 1), y que el grafo de Turán es el único de tales grafos extremales. El teorema de Erdős-Stone extiende este resultado a H  =  K _r ( t ), el grafo r -partito completo con t vértices en cada clase, que es el grafo obtenido al tomar K _r y reemplazar 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 grafo 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 grafo de Turán T ( n , r  − 1 ), ya que este grafo y, por lo tanto, cada uno de sus subgrafos se pueden colorear con r  − 1 colores. De ello se deduce que el número extremal 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 extremal para K _r ( t ); es decir,

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

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

Densidad de Turán

Otra forma de describir el teorema de Erdős-Stone es utilizando la densidad de Turán de un grafo , que se define por . Esto determina el número extremal hasta un término de error aditivo. También se puede pensar de la siguiente manera: dada una secuencia de grafos , cada uno de los cuales no contiene , tal que el número de vértices tiende 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 grafos, mostrando que cualquier grafo 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 demostración 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 que sea libre de π y mostrando que el hipergrafo tiene un número acotado de aristas. El teorema de Kővári-Sós-Turán dice, entre otras cosas, que el número extremal de π , el grafo bipartito completo con vértices en cada parte, es como máximo para una constante π . Esto se puede extender a los hipergrafos: definiendo π como el grafo -partito con vértices en cada parte, entonces para una constante π . ^{[ cita requerida ]} ${\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 grafo dado con , y algún grafo con vértices que no contiene un subgrafo isomorfo a , definimos el -grafo con los mismos vértices que y una hiperarista entre los vértices en si forman una camarilla en . Nótese que si contiene una copia de , entonces el grafo 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 lo tanto tiene hiperaristas, lo que indica que hay copias de en . Por sobresaturación, esto significa que la densidad de aristas de está dentro de la densidad de Turán de , que es por el teorema de Turán ; por lo tanto, la densidad de aristas está acotada por encima por . ${\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 otra parte, podemos lograr este límite 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 el t más grande tal que todo grafo 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. El orden correcto de s _{r ,ε} ( n ) en términos de n fue encontrado por Bollobás y Erdős: ^[4] para cualquier r y ε dados existen 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] determinaron luego 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. ; Stone, AH (1946). "Sobre la estructura de los grafos lineales". Boletín de la Sociedad Matemática Americana . 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 grafos de aristas". 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.