In
extremal graph theory
Extremal graph theory is a branch of combinatorics, itself an area of mathematics, that lies at the intersection of extremal combinatorics and graph theory. In essence, extremal graph theory studies how global properties of a graph influence local ...
, the Erdős–Stone theorem is an
asymptotic result generalising
Turán's theorem
In graph theory, Turán's theorem bounds the number of edges that can be included in an undirected graph that does not have a complete subgraph of a given size. It is one of the central results of extremal graph theory, an area studying the large ...
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”.
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 In extremal graph theory, the forbidden subgraph problem is the following problem: given a graph G, find the maximal number of edges \operatorname(n,G) an n-vertex graph can have such that it does not have a Glossary of graph theory#Subgraphs, subgr ...
for more examples of problems involving the extremal number. Turán's theorem says that ex(''n''; ''K''
''r'') = ''t''
''r'' − 1(''n''), the number of edges of the
Turán graph
The Turán graph, denoted by T(n,r), is a complete multipartite graph; it is formed by partitioning a set of n vertices into r subsets, with sizes as equal as possible, and then connecting two vertices by an edge if and only if they belong to di ...
''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=K
r''(''t''), the complete ''r''-partite graph with ''t'' vertices in each class, which is the graph obtained by taking ''K
r'' and replacing each vertex with ''t'' independent vertices:
:
Statement for arbitrary non-bipartite graphs
If ''H'' is an arbitrary graph whose
chromatic number
In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices ...
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), 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 ''K''
''r''(''t''); that is,
:
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''(''n''
2), and for general bipartite graphs little more is known. See
Zarankiewicz problem for more on the extremal functions of bipartite graphs.
Turán density
Another way of describing the Erdős–Stone theorem is using the Turán density of a graph
, which is defined by
. This determines the extremal number
up to an additive
error term. It can also be thought of as follows: given a sequence of graphs
, each not containing
, 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
with chromatic number
has a Turán density of
Proof
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
-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
, the complete bipartite graph with
vertices in each part, is at most
for a constant
. This can be extended to hypergraphs: defining
to be the
-partite
-graph with
vertices in each part, then
for some constant
.
Now, for a given graph
with
, and some graph
with
vertices that does not contain a subgraph isomorphic to
, we define the
-graph
with the same vertices as
and a hyperedge between vertices in
if they form a
clique
A clique ( AusE, CanE, or ), in the social sciences, is a group of individuals who interact with one another and share similar interests. Interacting with cliques is part of normative social development regardless of gender, ethnicity, or popular ...
in
. Note that if
contains a copy of
, then the original graph
contains a copy of
, as every pair of vertices in distinct parts must have an edge, but no two vertices in the same part contain an edge. Thus.
contains no copies of
, and so it has
hyperedges, indicating that there are
copies of
in
. By supersaturation, this means that the edge density of
is within
of the Turán density of
, which is
by
Turán's theorem
In graph theory, Turán's theorem bounds the number of edges that can be included in an undirected graph that does not have a complete subgraph of a given size. It is one of the central results of extremal graph theory, an area studying the large ...
; thus, the edge density is bounded above by
.
On the other hand, we can achieve this bound by taking the
Turán graph
The Turán graph, denoted by T(n,r), is a complete multipartite graph; it is formed by partitioning a set of n vertices into r subsets, with sizes as equal as possible, and then connecting two vertices by an edge if and only if they belong to di ...
, which contains no copies of
but has
edges, showing that this value is the maximum and concluding the proof.
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 ''s''
''r'',ε(''n'') (for 0 < ε < 1/(2(''r'' − 1))) to be the greatest ''t'' such that every graph of order ''n'' and size
:
contains a ''K''
''r''(''t'').
Erdős and Stone proved that
:
for ''n'' sufficiently large. The correct order of ''s''
''r'',ε(''n'') in terms of ''n'' was found by Bollobás and Erdős: 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
then determined the nature of the dependence on ''r'' and ε, up to a constant:
:
for sufficiently large ''n''.
Notes
{{DEFAULTSORT:Erdos-Stone theorem
Extremal graph theory
Theorems in graph theory
Stone theorem