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, and it has been described as the “fundamental theorem of extremal graph theory”.
Article
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, and it has been described as the “fundamental theorem of extremal graph theory”.
Contents
Statement for Turán graphs
The extremal number ex(n; H) is defined to be the maximum number of edges in a graph with n vertices not containing a subgraph isomorphic to H; see the Forbidden subgraph problem for more examples of problems involving the extremal number. Turán's theorem says that ex(n; Kr) = tr − 1(n), the number of edges of the Turán graph T(n, r − 1), and that the Turán graph is the unique such extremal graph. The Erdős–Stone theorem extends this result to H = Kr(t), the complete r-partite graph with t vertices in each class, which is the graph obtained by taking Kr and replacing each vertex with t independent vertices:
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), as this graph and therefore each of its subgraphs can be colored with r − 1 colors.
It follows that the extremal number 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,
One proof of the Erdős–Stone theorem uses an extension of the Kővári–Sós–Turán theorem to hypergraphs, as well as the supersaturation theorem, by creating a corresponding hypergraph for every graph that is
K
r
(
t
)
{\displaystyle K_{r}(t)}
-free and showing that the hypergraph has some bounded number of edges. The Kővári–Sós–Turán says, among other things, that the extremal number of
K
2
(
t
)
{\displaystyle K_{2}(t)}
, the complete bipartite graph with
t
{\displaystyle t}
vertices in each part, is at most
ex
(
K
2
(
t
)
;
n
)
≤
C
Counting Paths
Another proof of the Erdős–Stone theorem works by generalising the proof of the Kővári–Sós–Turán theorem, counting paths of length two in a high minimum degree subgraph of the original graph
G
{\displaystyle G}
. This starts with a lemma to find a subgraph with high minimum degree, then a lemma that finds an
r
{\displaystyle r}
-partite Turán graph given a graph with high minimum degree, and finally the application of both lemmas to prove the Erdős–Stone theorem.
For purposes of notation, let
V
(
G
)
{\displaystyle V(G)}
be the set of vertices of a graph
G
{\displaystyle G}
and
e
(
G
)
{\displaystyle e(G)}
be the number of edges of a graph
G
{\displaystyle G}
.
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 sr,ε(n) (for 0 < ε < 1/(2(r − 1))) to be the greatest t such that every graph of order n and size
Article from Wikipedia (CC BY-SA 4.0), where it is maintained by volunteer editors.
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(n; H) = o(n2), and for general bipartite graphs little more is known. See Zarankiewicz problem for more on the extremal functions of bipartite graphs.
up to an additive
o
(
n
2
)
{\displaystyle o(n^{2})}
error term. It can also be thought of as follows: given a sequence of graphs
G
1
,
G
2
,
…
{\displaystyle G_{1},G_{2},\dots }
, each not containing
H
{\displaystyle H}
, such that the number of vertices goes to infinity, the Turán density is the maximum possible limit of their edge densities. The Erdős–Stone theorem determines the Turán density for all graphs, showing that any graph
for n sufficiently large. The correct order of sr,ε(n) in terms of n was found by Bollobás and Erdős: 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 then determined the nature of the dependence on r and ε, up to a constant:
