Theorem

Erdos-Stone Theorem

Combinatorics and Graph Theory

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

Statement

The 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

Proof Year

1946 1

Classification

Statement Form

Inequality 1

Connections

Has Statement Form

Inequality

In Branch

Graph Theory

Source Erdos-Stone theorem, Wikipedia

Proved By

Paul Erdos

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".
In Branch: Graph Theory, Lead sentence

Switch Atlas

The Inner World

The Civil World

The Natural World

Erdos-Stone Theorem

Has Statement Form

In Branch

Proved By