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. 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”. The extremal function ex(n; H) is defined to be the maximum number of edges in a graph of order n not containing a subgraph isomorphic to H.

PropertyValue
dbpprop:abstract
  • 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. 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”. The extremal function ex(n; H) is defined to be the maximum number of edges in a graph of order n not containing a subgraph isomorphic to H. Turán's theorem says that ex(n; Kr) = tr − 1(n), the order of the Turán graph, and that the Turán graph is the unique extremal graph. The Erdős-Stone theorem extends this to Kr(t), the complete r-partite graph with t vertices in each class, or equivalently the Turán graph T(rt,r): <math>\mbox{ex}(n; K_r) = \left(\frac{r-2}{r-1} + o \right){n\choose2}. </math> An immediate corollary is that this applies to any graph H with chromatic number r, since such a graph is contained in Kr(t) for sufficiently large t but is not contained in any Turán graph Tr-1(n). For bipartite graphs H, however, the theorem gives only the limited information that ex(n; H) = o(n), and for general bipartite graphs little more is known.
dbpprop:hasPhotoCollection
rdf:type
rdfs:comment
  • 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. 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”. The extremal function ex(n; H) is defined to be the maximum number of edges in a graph of order n not containing a subgraph isomorphic to H.
rdfs:label
  • Erdős–Stone theorem
owl:sameAs
skos:subject
foaf:page
is dbpprop:redirect of
is owl:sameAs of