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 theStatement for 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), 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, : ForTurá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 ofProof
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 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; thus, the edge density is bounded above by . On the other hand, we can achieve this bound by taking the Turán graph , 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