- Erdős–Stone theorem
In

extremal graph theory , the**Erdős–Stone theorem**is anasymptotic result generalisingTurán's theorem to bound the number of edges in an "H"-free graph for a non-complete graph "H". It is named afterPaul 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=*] and it has been described as the “fundamental theorem of extremal graph theory”. [Bulletin of the American Mathematical Society |volume=52 |pages=1087–1091 |doi=10.1090/S0002-9904-1946-08715-7*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. 120The 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 theTurá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 theTurá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"^{2}), 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=*] "s"Elsevier |isbn=0-444-88002-X |pages=p. 1244 |chapter=Extremal graph theory_{"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\; 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",ε}("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=*] : for any given "r" and ε there are constants "c"Bulletin of the London Mathematical Society |volume=5 |pages=317–321 |doi=10.1112/blms/5.3.317_{1}("r", ε) and "c"_{2}("r", ε) such that "c"_{1}("r", ε) log "n" < "s"_{"r",ε}("n") < "c"_{2}("r", ε) 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=*] then determined the nature of the dependence on "r" and ε, up to a constant::$frac\{1\}\{500log(1/varepsilon)\}log\; n\; <\; s\_\{r,varepsilon\}(n)\; <\; frac\{5\}\{log(1/varepsilon)\}log\; n$ for sufficiently large "n".Journal of the London Mathematical Society |volume=23 |issue=2 |pages=207–214 |doi=10.1112/jlms/s2-23.2.207**References**

*Wikimedia Foundation.
2010.*

### Look at other dictionaries:

**List of things named after Paul Erdős**— The following were named after Paul Erdős:* Erdős number * Erdős cardinal * Erdős conjecture a list of numerous conjectures named after Erdős ** Erdős conjecture on arithmetic progressions ** Cameron–Erdős conjecture ** Erdős–Burr conjecture **… … Wikipedia**Turán's theorem**— In graph theory, Turán s theorem is a result on the number of edges in a Kr+1 free graph. An n vertex graph that does not contain any (r + 1) vertex clique may be formed by partitioning the set of vertices into r parts of equal or… … Wikipedia**Arthur Harold Stone**— (September 30 1916 ndash; August 6 2000) was a British mathematician born in London, who worked mostly in topology. His wife was American mathematician Dorothy Maharam. His first paper dealt with squaring the square. He proved the Erdős Stone… … Wikipedia**Paul Erdős**— auf einem Seminar in Budapest (Herbst 1992) Paul Erdős [ˈɛrdøːʃ] (ungarisch Erdős Pál; * 26. März 1913 in Budapest, Österreich Ungarn; † 20. September … Deutsch Wikipedia**Paul Erdos**— Paul Erdős auf einem Seminar in Budapest (Herbst 1992) Paul Erdős [ˈɛrdøːʃ] (ungarisch: Erdős Pál) (* 26. März 1913 in Budapest, Ungarn; † 20. September 1996 in Warschau, Polen) war … Deutsch Wikipedia**Paul Erdös**— Paul Erdős auf einem Seminar in Budapest (Herbst 1992) Paul Erdős [ˈɛrdøːʃ] (ungarisch: Erdős Pál) (* 26. März 1913 in Budapest, Ungarn; † 20. September 1996 in Warschau, Polen) war … Deutsch Wikipedia**Tychonoff's theorem**— For other theorems named after Tychonoff, see Tychonoff s theorem (disambiguation). In mathematics, Tychonoff s theorem states that the product of any collection of compact topological spaces is compact. The theorem is named after Andrey… … Wikipedia**List of theorems**— This is a list of theorems, by Wikipedia page. See also *list of fundamental theorems *list of lemmas *list of conjectures *list of inequalities *list of mathematical proofs *list of misnamed theorems *Existence theorem *Classification of finite… … Wikipedia**List of mathematics articles (E)**— NOTOC E E₇ E (mathematical constant) E function E₈ lattice E₈ manifold E∞ operad E7½ E8 investigation tool Earley parser Early stopping Earnshaw s theorem Earth mover s distance East Journal on Approximations Eastern Arabic numerals Easton s… … Wikipedia**Turán graph**— The Turán graph T(13,4) Named after Pál Turán v · … Wikipedia