Erdős–Stone theorem

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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[edit]

The extremal function ex(nH) 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(nKr) = tr − 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 Kr(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[edit]

If H is an arbitrary graph whose chromatic number is r > 2, then H is contained in Kr(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 Kr(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(nH) = o(n2), and for general bipartite graphs little more is known. See Zarankiewicz problem for more on the extremal functions of bipartite graphs.

Quantitative results[edit]

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] sr(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 Kr(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 sr(n) in terms of n was found by Bollobás and Erdős:[4] for any given r and ε there are constants c1(r, ε) and c2(r, ε) such that c1(r, ε) log n < sr(n) < c2(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[edit]

  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.