Odd–even sort

2014-01-19T17:11:23Z

88.78.14.27: /* Proof of Correctness */

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 (mathematician)|Arthur Stone]], who proved it in 1946,<ref>{{cite journal |last=Erdős |first=P. |authorlink=Paul Erdős |coauthors=[[Arthur Stone (mathematician)|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 |issue=12}}</ref> and it has been described as the “fundamental theorem of extremal graph theory”.<ref>{{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=120}}</ref>

==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'')):

:<math>\mbox{ex}(n; K_r(t)) = \left( \frac{r-2}{r-1} + o(1) \right){n\choose2}.</math>

==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,
:<math>\mbox{ex}(n; H) = \left( \frac{r-2}{r-1} + o(1) \right){n\choose2}.</math>

For [[bipartite graph]]s ''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''2), 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 [[Little-o notation|''o''(1)]] term. Define the notation<ref>{{cite book |last=Bollobás |first=Béla |authorlink=Béla Bollobás |editor= [[Ronald Graham|R. L. Graham]], M. Grötschel and [[László Lovász|L. Lovász]] (eds.) |title=Handbook of combinatorics |year=1995 |publisher=[[Elsevier]] |isbn=0-444-88002-X |pages=1244 |chapter=Extremal graph theory}}</ref> ''s''''r'',ε(''n'') (for 0 < ε < 1/(2(''r'' − 1))) to be the greatest ''t'' such that every graph of order ''n'' and size

:<math>\left( \frac{r-2}{2(r-1)} + \varepsilon \right)n^2</math>

contains a ''K''''r''(''t'').

Erdős and Stone proved that
:<math>s_{r,\varepsilon}(n) \geq \left(\underbrace{\log\cdots\log}_{r-1} n\right)^{1/2}</math>
for ''n'' sufficiently large. The correct order of ''s''''r'',ε(''n'') in terms of ''n'' was found by Bollobás and Erdős:<ref>{{cite journal |last=Bollobás |first=B. |authorlink=Béla Bollobás |coauthors=[[Paul Erdős|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 |issue=3}}</ref> for any given ''r'' and ε there are constants ''c''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<ref>{{cite journal |last=Chvátal |first=V. |authorlink=Václav Chvátal |coauthors=[[Endre Szemerédi|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}}</ref> then determined the nature of the dependence on ''r'' and ε, up to a constant:
:<math>\frac{1}{500\log(1/\varepsilon)}\log n < s_{r,\varepsilon}(n) < \frac{5}{\log(1/\varepsilon)}\log n</math> for sufficiently large ''n''.

==Notes==
{{reflist}}

{{DEFAULTSORT:Erdos-Stone theorem}}
[[Category:Extremal graph theory]]
[[Category:Theorems in graph theory]]
[[Category:Paul Erdős]]

formulasearchengine - User contributions [en]

Odd–even sort