Turán's theorem

Turán's theorem gives the maximum number of edges in a graph with a fixed number of vertices and no clique of a specified size. Equality is attained by a balanced complete multipartite graph.

Turán graph: A complete multipartite graph whose part sizes differ by at most one. This balanced graph attains the edge maximum in Turán's theorem.
Simple graph: A graph with no loops and at most one edge between any pair of vertices. Turán's theorem concerns edge counts in finite simple graphs.
Pál Turán: Hungarian mathematician Pál Turán (1910–1976), known for foundational work in extremal graph theory. He proved the theorem in 1941 while studying a problem in analytic number theory.
Zarankiewicz problem: The problem of maximizing edges in a bipartite graph while avoiding a fixed complete bipartite graph. It transplants the forbidden-subgraph question to bipartite graphs.
Erdős–Stone–Simonovits theorem: An asymptotic extremal theorem whose leading edge-density term depends on a forbidden graph's chromatic number. It gives a broad asymptotic analogue where exact Turán graphs need not apply.
Clique number: The largest number of vertices in a graph that are pairwise adjacent. The forbidden clique size sets the multipartite structure and edge bound.
Clique: A set of vertices in a graph in which every pair is adjacent. A complete subgraph is precisely the structure the theorem forbids.
Paul Erdős: Hungarian mathematician Paul Erdős (1913–1996), whose work shaped combinatorics and graph theory. His later results extended the extremal questions that Turán's theorem made central.
Kővári–Sós–Turán theorem: An upper bound on edges in graphs or bipartite graphs that avoid a fixed complete bipartite graph. It extends Turán-style edge bounds to forbidden complete bipartite subgraphs.
Stability theorem: A result showing that structures close to an extremal bound must resemble extremal examples. Stability strengthens Turán's theorem by characterizing near-maximal graphs.

Linked from 4 pages