Erdős–Stone theorem


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"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=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"1("r", &epsilon;) and "c"2("r", &epsilon;) such that "c"1("r", &epsilon;) log "n" &lt; "s""r",&epsilon;("n") &lt; "c"2("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::frac{1}{500log(1/varepsilon)}log n < s_{r,varepsilon}(n) < frac{5}{log(1/varepsilon)}log n for sufficiently large "n".

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


Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.