Erdős–Stone theorem

In extremal graph theory, the Erdős–Stone theorem is an asymptotic result generalising Turán's theorem to bound the number of edges in an H-free graph for a non-complete graph H. It is named after Paul Erdős and Arthur Stone, who proved it in 1946,^[1] and it has been described as the “fundamental theorem of extremal graph theory”.^[2]

Extremal functions of Turán graphs

The extremal function ex(n; H) is defined to be the maximum number of edges in a graph of order n not containing a subgraph isomorphic to H. Turán's theorem says that ex(n; K_r) = t_r − 1(n), the order of the Turán graph, and that the Turán graph is the unique extremal graph. The Erdős–Stone theorem extends this to graphs not containing K_r(t), the complete r-partite graph with t vertices in each class (equivalently the Turán graph T(rt,r)):

$\mbox{ex}(n; K_r(t)) = \left( \frac{r-2}{r-1} + o(1) \right){n\choose2}.$

Extremal functions of arbitrary non-bipartite graphs

If H is an arbitrary graph whose chromatic number is r > 2, then H is contained in K_r(t) whenever t is at least as large as the largest color class in an r-coloring of H, but it is not contained in the Turán graph T(n,r − 1) (because every subgraph of this Turán graph may be colored with ,r − 1 colors). It follows that the extremal function for H is at least as large as the number of edges in T(n,r − 1), and at most equal to the extremal function for K_r(t); that is,

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

For bipartite graphs H, however, the theorem does not give a tight bound on the extremal function. It is known that, when H is bipartite, ex(n; H) = o(n²), and for general bipartite graphs little more is known. See Zarankiewicz problem for more on the extremal functions of bipartite graphs.

Quantitative results

Several versions of the theorem have been proved that more precisely characterise the relation of n, r, t and the o(1) term. Define the notation^[3] s_r,ε(n) (for 0 < ε < 1/(2(r − 1))) to be the greatest t such that every graph of order n and size

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

contains a K_r(t).

Erdős and Stone proved that

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

for n sufficiently large. The correct order of s_r,ε(n) in terms of n was found by Bollobás and Erdős:^[4] for any given r and ε there are constants c₁(r, ε) and c₂(r, ε) such that c₁(r, ε) log n < s_r,ε(n) < c₂(r, ε) log n. Chvátal and Szemerédi^[5] then determined the nature of the dependence on r and ε, up to a constant:

$\frac{1}{500\log(1/\varepsilon)}\log n < s_{r,\varepsilon}(n) < \frac{5}{\log(1/\varepsilon)}\log n$ for sufficiently large n.

Notes

1. Erdős, P.; Stone, A. H. (1946). "On the structure of linear graphs". Bulletin of the American Mathematical Society 52 (12): 1087–1091. doi:10.1090/S0002-9904-1946-08715-7.
2. Bollobás, Béla (1998). Modern Graph Theory. New York: Springer-Verlag. p. 120. ISBN 0-387-98491-7.
3. Bollobás, Béla (1995). "Extremal graph theory". In R. L. Graham, M. Grötschel and L. Lovász (eds.). Handbook of combinatorics. Elsevier. p. 1244. ISBN 0-444-88002-X.
4. Bollobás, B.; Erdős, P. (1973). "On the structure of edge graphs". Bulletin of the London Mathematical Society 5 (3): 317–321. doi:10.1112/blms/5.3.317.
5. Chvátal, V.; Szemerédi, E. (1981). "On the Erdős-Stone theorem". Journal of the London Mathematical Society 23 (2): 207–214. doi:10.1112/jlms/s2-23.2.207.