Erdős–Stone theorem
E554300
The Erdős–Stone theorem is a fundamental result in extremal graph theory that asymptotically determines the maximum number of edges in an n-vertex graph that avoids containing a given subgraph.
Statements (41)
| Predicate | Object |
|---|---|
| instanceOf |
result in extremal graph theory
ⓘ
theorem ⓘ |
| appliesTo |
finite simple graphs
ⓘ
n-vertex graphs ⓘ |
| assumes | fixed forbidden graph H independent of n ⓘ |
| characterizes | maximum number of edges in an n-vertex graph avoiding a fixed subgraph ⓘ |
| classification | cornerstone of modern extremal combinatorics ⓘ |
| concerns |
Turán-type extremal problems
ⓘ
asymptotic edge density ⓘ extremal number of edges in graphs ⓘ forbidden subgraphs ⓘ |
| domain | n → ∞ asymptotic regime ⓘ |
| field |
extremal graph theory
ⓘ
graph theory ⓘ |
| generalizes | Turán’s theorem NERFINISHED ⓘ |
| givesAsymptoticsFor | extremal function ex(n,H) ⓘ |
| hasVariant | Erdős–Stone–Simonovits theorem NERFINISHED ⓘ |
| implies |
extremal edge density depends only on chromatic number of forbidden graph for non-bipartite H
ⓘ
graphs with many edges contain large complete multipartite subgraphs ⓘ |
| influenced | development of extremal graph theory ⓘ |
| involvesConcept |
chromatic number χ(H)
ⓘ
edge density ⓘ forbidden subgraph H ⓘ o(1) term in asymptotics ⓘ |
| isDescribedAs |
asymptotic solution to general Turán-type problems for non-bipartite graphs
ⓘ
fundamental result in extremal graph theory ⓘ |
| namedAfter |
Arthur H. Stone
NERFINISHED
ⓘ
Paul Erdős NERFINISHED ⓘ |
| originalAuthors |
Arthur H. Stone
NERFINISHED
ⓘ
Paul Erdős NERFINISHED ⓘ |
| publishedIn | Proceedings of the London Mathematical Society NERFINISHED ⓘ |
| relatedConcept | complete (χ(H)-1)-partite Turán graph ⓘ |
| relatesTo |
Turán’s theorem
NERFINISHED
ⓘ
chromatic number of a graph ⓘ |
| saysAsymptoticallyEquivalentTo | edge number of Turán graph T_{χ(H)-1}(n) for non-bipartite H ⓘ |
| statesThat | for every non-bipartite graph H, ex(n,H) = (1 - 1/(χ(H)-1) + o(1)) * n^2 / 2 ⓘ |
| topic | forbidden subgraph problems in dense graphs ⓘ |
| typeOfResult | asymptotic extremal bound ⓘ |
| usedFor |
estimating extremal numbers for non-bipartite forbidden graphs
ⓘ
proving existence of dense substructures in graphs ⓘ |
| yearProved | 1946 ⓘ |
Referenced by (1)
Full triples — surface form annotated when it differs from this entity's canonical label.