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, [cite journal |last=Erdős |first=P. |authorlink=Paul Erdős |coauthors=Stone, A. H. |year=1946 |title=On the structure of linear graphs |journal=Bulletin of the American Mathematical Society |volume=52 |pages=1087–1091 |doi=10.1090/S0002-9904-1946-08715-7] and it has been described as the “fundamental theorem of extremal graph theory”. [cite book |last=Bollobás |first=Béla |authorlink=Béla Bollobás |title=Modern Graph Theory |year=1998 |publisher=Springer-Verlag |location=New York |isbn=0-387-98491-7 |pages=p. 120]

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 "K"_"r"("t"), the complete "r"-partite graph with "t" vertices in each class, or equivalently the Turán graph "T"("rt","r"):

:$mbox\{ex\}(n;\; K\_r(t))\; =\; left(\; frac\{r-2\}\{r-1\}\; +\; o(1)\; ight)\{nchoose2\}.$

An immediate corollary is that this applies to "any" graph "H" with chromatic number "r", since such a graph is contained in "K"_"r"("t") for sufficiently large "t" but is not contained in any Turán graph "T"_"r"-1("n"). For bipartite graphs "H", however, the theorem gives only the limited information that ex("n"; "H") = "o"("n"²), and for general bipartite graphs little more is known.

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 [cite book |last=Bollobás |first=Béla |authorlink=Béla Bollobás |editor= R. L. Graham, M. Grötschel and L. Lovász (eds.) |title=Handbook of combinatorics |year=1995 |publisher=Elsevier |isbn=0-444-88002-X |pages=p. 1244 |chapter=Extremal graph theory] "s"_{"r",&epsilon;}("n") (for 0 < &epsilon; < 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\; ight)n^2$

contains a "K"_"r"("t").

Erdős and Stone proved that:$s\_\{r,varepsilon\}(n)\; geq\; left(underbrace\{logcdotslog\}\_\{r-1\}\; n\; ight)^\{1/2\}$for "n" sufficiently large. The correct order of "s"_{"r",&epsilon;}("n") in terms of "n" was found by Bollobás and Erdős [cite journal |last=Bollobás |first=B. |authorlink=Béla Bollobás |coauthors=Erdős, P. |year=1973 |title=On the structure of edge graphs |journal=Bulletin of the London Mathematical Society |volume=5 |pages=317–321 |doi=10.1112/blms/5.3.317] : for any given "r" and &epsilon; there are constants "c"₁("r", &epsilon;) and "c"₂("r", &epsilon;) such that "c"₁("r", &epsilon;) log "n" &lt; "s"_{"r",&epsilon;}("n") &lt; "c"₂("r", &epsilon;) log "n". Chvátal and Szemerédi [cite journal |last=Chvátal |first=V. |authorlink=Václav Chvátal |coauthors=Szemerédi, E. |year=1981 |title=On the Erdős-Stone theorem |journal=Journal of the London Mathematical Society |volume=23 |issue=2 |pages=207–214 |doi=10.1112/jlms/s2-23.2.207] then determined the nature of the dependence on "r" and &epsilon;, up to a constant:: for sufficiently large "n".

References