Erdős–Stone theorem

The Erdős–Stone theorem states that for fixed graph H with chromatic number r+1, the maximum number of edges in an n-vertex H-free graph is (1−1/r+o(1)) binom(n,2) as n grows.

Turán's theorem: Forbidding a complete graph K_{r+1} gives an extremal graph with asymptotically (1−1/r) binom(n,2) edges. The theorem extends this density formula from forbidden cliques to every graph with the same chromatic number.
Paul Erdős: A Hungarian mathematician who made foundational contributions to combinatorics, number theory, and probability. He co-developed the theorem that bears his name and shaped its probabilistic perspective.
Extremal number: The maximum number of edges in a graph of given order that avoids a specified subgraph. The theorem gives the leading asymptotic term of this quantity for every fixed forbidden graph.
Exact extremal graph: A graph attaining the maximum edge count while avoiding a specified subgraph. The theorem predicts asymptotic density, not the exact extremal construction for every forbidden graph.
Complete multipartite graph: A graph whose vertices divide into independent sets, with every pair from different sets adjacent. Large complete multipartite graphs provide the structured subgraphs forced by high edge density.
Arthur Stone: An American mathematician whose work included foundational results in combinatorics and topology. He co-authored the theorem with Erdős.
Triangle-free graph: A graph containing no three mutually adjacent vertices. Its extremal edge count is an exact instance of the theorem's clique-specialized density.
Kővári–Sós–Turán theorem: An upper-bound theorem for the number of edges in graphs avoiding a fixed complete bipartite subgraph. For bipartite forbidden graphs, this theorem supplies subquadratic bounds where Erdős–Stone's density term vanishes.
Regularity lemma: A graph decomposition theorem that approximates large graphs by a bounded number of quasirandom pairs of vertex sets. Regularity methods turn density assumptions into a reduced graph where multipartite structure can be found.
Extremal graph theory: The study of how large or structured a graph can be while avoiding specified subgraphs or properties. The theorem is a landmark result in this field's study of forbidden-subgraph limits.

Linked from 3 pages