En la teoría de grafos extremos , el teorema de Erdős-Stone es un resultado asintótico que generaliza el teorema de Turán para acotar el número de aristas en un gráfico libre de H para un gráfico H no completo . Lleva el nombre de Paul Erdős y Arthur Stone , quienes lo probaron en 1946, [1] y ha sido descrito como el "teorema fundamental de la teoría de grafos extremos". [2]
Funciones extremas de las gráficas de Turán
La función extremal ex ( n ; H ) se define como el número máximo de bordes en un gráfico de orden n que no contiene un subgrafo isomorfo a H . El teorema de Turán dice que ex ( n ; K r ) = t r - 1 ( n ), el orden de la gráfica de Turán , y que la gráfica de Turán es la gráfica extrema única. El teorema de Erdős-Stone extiende esto a las gráficas que no contienen K r ( t ), la gráfica r -partita completa con t vértices en cada clase (de manera equivalente, la gráfica de Turán T ( rt , r )):
Funciones extremas de grafos 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) (porque cada subgráfico de este gráfico de Turán se puede colorear con r - 1 colores). De ello se deduce que la función extrema para H es al menos tan grande como el número de aristas en T ( n , r - 1), y como mucho igual a la función extrema para K r ( t ); es decir,
Para grafos bipartitos H , sin embargo, el teorema no da un apretado unido en la función extremal. Se sabe que, cuando H es bipartito, ex ( n ; H ) = o ( n 2 ), y para grafos bipartitos generales se sabe poco más. Consulte el problema de Zarankiewicz para obtener más información sobre las funciones extremas de los gráficos bipartitos.
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 t mayor, de modo que cada gráfica de orden ny tamaño
contiene una K r ( t ).
Erdős y Stone demostraron que
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 ε hay constantes c 1 ( r , ε) y c 2 ( r , ε) tales que c 1 ( r , ε) log n < s r , ε ( n ) < c 2 ( r , ε) log n . Luego, Chvátal y Szemerédi [5] determinaron la naturaleza de la dependencia de r y ε, hasta una constante:
- para n suficientemente grande .
Notas
- ^ Erdős, P .; Stone, AH (1946). "Sobre la estructura de los gráficos lineales" . Boletín de la American Mathematical Society . 52 (12): 1087–1091. doi : 10.1090 / S0002-9904-1946-08715-7 .
- ^ Bollobás, Béla (1998). Teoría de grafos moderna . Nueva York: Springer-Verlag . págs. 120 . ISBN 0-387-98491-7.
- ^ 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.
- ^ Bollobás, B .; Erds, P. (1973). "Sobre la estructura de los gráficos de borde". Boletín de la London Mathematical Society . 5 (3): 317–321. doi : 10.1112 / blms / 5.3.317 .
- ^ 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 .