Teorema de Erdős–Stone

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

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

Para grafos bipartitos ${\displaystyle H}$, sin embargo, el teorema no da un límite apretado en la función extremal. Se conoce que, cuando ${\displaystyle H}$ es bipartito, ${\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 ${\displaystyle n}$, ${\displaystyle r}$, ${\displaystyle t}$ y el término ${\displaystyle o(1)}$. Define la notación^[3] ${\displaystyle s_{r,\varepsilon }(n)}$ para ${\displaystyle 0<\varepsilon <{\tfrac {1}{2(r-1)}}}$ para ser la ${\displaystyle t}$ mayor de modo que cada grafo de orden ${\displaystyle n}$ y tamaño

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

contenga a ${\displaystyle K_{r}(t)}$.

Erdős y Stone probaron que

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

para un ${\displaystyle n}$ suficientemente grande. El orden correcto de ${\displaystyle s_{r,\varepsilon }(n)}$ en términos de ${\displaystyle n}$ fue encontrada por Bollobás y Erdős:^[4] para cada ${\displaystyle r}$ y ${\displaystyle \varepsilon }$ dados; existen constantes ${\displaystyle c_{1}(r,\varepsilon )}$ y ${\displaystyle c_{2}(r,\varepsilon )}$ de forma que ${\displaystyle c_{1}(r,\varepsilon )\ log\ n<s_{r,\varepsilon }(n)<c_{2}(r,\varepsilon )\ log\ n}$. Chvátal y Szemerédi^[5] luego determinaron la naturaleza de ${\displaystyle r}$ y ${\displaystyle \varepsilon }$ hasta una constante

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

para una ${\displaystyle n}$ suficientemente grande.