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
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”.
e x ( n ,
{\displaystyle ex(n,H)}
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
e x ( n ,
, 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
vértices en cada clase (equivalentemente, el grafo de Turán
es un grafo arbitrario cuyo número cromático
es al menos igual de grande que la clase de color más grande en una
, 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
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
e x ( n ,
{\displaystyle ex(n,H)=o(n^{2})}
, 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.
Muchas versiones del teorema han probado que más precisamente caracteriza la relación de
y tamaño contenga a
Erdős y Stone probaron que para un
fue encontrada por Bollobás y Erdős:[4] para cada
Chvátal y Szemerédi[5] luego determinaron la naturaleza de