The Erdos-Stone Theorem gives the asymptotic maximum number of edges a graph on n vertices can have while still avoiding a fixed forbidden subgraph, expressing that maximum as a fraction of the total possible edges determined by the forbidden subgraph's chromatic number, plus a smaller error term that vanishes as n grows. Named for Paul Erdos and Arthur Stone, it is the central asymptotic result of extremal graph theory, extending the earlier Turán's Theorem, which addresses only the special case of forbidding a complete graph.
Facts
StatementThe Erdos-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. 1 Classification
Statement Form Connections
Has Statement Form
In Branch
Source Erdos-Stone theorem, Wikipedia
Principal Result Of
Source Erdos-Stone theorem, Wikipedia
Proved By
Sources
1. Erdos-Stone theorem, Wikipedia
Lead section
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.
Lead section
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".
Principal Result Of: Paul Erdos, Lead sentence of the article on the result
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”.
- In Branch: Graph Theory, Lead sentence
View the SourceReader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.