Teorema de Erdős–Stone

En la teoría de grafos extremales, el teorema de Erdős–Stone es un resultado asintótico generalizando el teorema de Turán para limitar el número de vértices en un grafo -libre por un grafo completo . Debe su nombre a 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 extremales”.[2]

Funciones extremales de los grafos de Turán

La función extremal está definido para ser el número máximo de aristas de orden , sin contener un subgrafo isomórfico a . El teorema de Turán dice que , el orden del grafo de Turán y que el grafo de Turán es el único grafo extremal. El teorema de Erdős–Stone extiende este a grafos que no contengan , el grafo complero -partito con vértices en cada clase (equivalentemente, el grafo de Turán ):

Funciones extremales de grafos no-bipartitos arbitrarios

Si es un grafo arbitrario cuyo número cromático , entonces es contenido en cuando es al menos igual de grande que la clase de color más grande en una -coloración de , pero no está contenida en el grafo de Turán (debido a que cada subgrafo de un grafo de Turán puede ser coloreado con colores). Resulta que todas las funciones extremales para es al menos igual de grande que el número de vértices en y, al menos, igual a la función extremal para ; esto es,

Para grafos bipartitos , sin embargo, el teorema no da un límite apretado en la función extremal. Se conoce que, cuando es bipartito, , y para grafos bipartitos generales poco más se conoce. Un problema que estudia mucho las funciones extremales de los grafos bipartitos, es el problema de Zarankiewicz.

Resultados cuantitativos

Muchas versiones del teorema han probado que más precisamente caracteriza la relación de , , y el término . Define la notación[3] para para ser la mayor de modo que cada grafo de orden y tamaño

contenga a .

Erdős y Stone probaron que

para un suficientemente grande. El orden correcto de en términos de fue encontrada por Bollobás y Erdős:[4] para cada y dados; existen constantes y de forma que . Chvátal y Szemerédi[5] luego determinaron la naturaleza de y hasta una constante

para una suficientemente grande.

Referencias

  1. Erdős, P.; Stone, A. H. (1946). «On the structure of linear graphs». Bulletin of the American Mathematical Society (en inglés) (American Mathematical Society) 52 (12): 1087-1091. doi:10.1090/S0002-9904-1946-08715-7.
  2. Bollobás, Béla. Modern Graph Theory (en inglés). Springer. p. 120. ISBN 978-1-4612-0619-4.
  3. Bollobás, Béla (1995). «Extremal graph theory». En Graham, R. L.; Grötschel, M.; Lovász, László, eds. Handbook of Combinatorics (en inglés). Elsevier. p. 1244. ISBN 978-0-444-82346-5.
  4. Bollobás, Béla; Erdős, P. (1973). «On the structure of edge graphs». Bulletin of the London Mathematical Society (en inglés) (London Mathematical Society) 5 (3): 317-321. doi:10.1112/blms/5.3.317.
  5. Chvátal, V.; Szemerédi, Endre (1981). «On the Erdős-Stone theorem». Journal of the London Mathematical Society (en inglés) (London Mathematical Society) 23 (2): 207-214. doi:10.1112/jlms/s2-23.2.207.
Este artículo ha sido escrito por Wikipedia. El texto está disponible bajo la licencia Creative Commons - Atribución - CompartirIgual. Pueden aplicarse cláusulas adicionales a los archivos multimedia.