Turán's theorem

Turán's theorem is a central result in Graph theory establishing the maximum number of edges in an n-vertex graph that does not contain a complete subgraph of a given size. The theorem, proved by Pál Turán in 1941, provided a definitive answer to an extremal problem that generalizes Mantel's theorem and stimulated developments linking Paul Erdős, Alfréd Rényi, and other figures in combinatorics. It plays a foundational role in the development of extremal graph theory and has deep connections to later milestones such as the Erdős–Stone theorem and work by Turán's contemporaries.

Statement and historical context

Turán's theorem states that for integers n and r ≥ 2, the maximum number of edges in an n-vertex simple graph with no copy of the complete graph K_r equals the number of edges in the complete (r−1)-partite balanced graph on n vertices. The problem grew out of earlier special cases: Mantel's theorem solved the r=3 case, while investigations by Pál Turán were motivated by questions pursued in the circles of Paul Erdős, Alfréd Rényi, Béla Bollobás, and the Hungarian Academy of Sciences. The theorem's influence extends to later results by Erdős–Stone and G. A. Dirac, and it informed approaches used in the work of Lovász, Szemerédi, and Komlós.

Proofs and methods

Multiple proofs of Turán's theorem exist, reflecting diverse methods in combinatorics. Turán's original proof used combinatorial double-counting and an averaging argument familiar in the writings of Pál Turán and contemporaries such as Paul Erdős and Alfréd Rényi. A common alternative uses the method of graph transformations and Zykov symmetrization, techniques associated with Zykov, and linked historically to the work of Turán and Zs. Sárközy. Another approach employs the probabilistic intuition developed by Paul Erdős and formalized in subsequent probabilistic methods; yet another fast proof arises via convexity arguments reminiscent of methods found in texts by Lovász and Béla Bollobás. Spectral techniques using eigenvalues, connected to research by Hoffman, provide algebraic proofs and link Turán-type bounds to the study of adjacency matrices pursued by Cvetković and Wilf.

Turán graphs and extremal construction

The extremal construction achieving equality is the Turán graph T_{n,r-1}, the complete (r−1)-partite graph with parts as equal as possible. This construction parallels earlier extremal constructions in work by Mantel and inspired systematic study of multipartite extremal examples by Erdős, Sós, and Simonovits. Properties of Turán graphs, including regularity, chromatic number, and independence number, have been analyzed in the literature by Bollobás, Diestel, and Douglas West, informing broader theory in texts by Béla Bollobás and János Pach.

Generalizations and related results

Turán's theorem catalyzed numerous generalizations and related theorems. The Erdős–Stone theorem extends Turán-type asymptotics to non-complete forbidden subgraphs and is sometimes called the fundamental theorem of extremal graph theory, developed by Paul Erdős and Arthur Stone. Stability results, such as those by Simonovits, characterize near-extremal graphs as close to Turán graphs, while the Zarankiewicz problem and results by Kővári–Sós–Turán address bipartite forbidden configurations. Hypergraph extensions, including results by Erdős and Frankl and the development of the Erdős–Ko–Rado theorem, expand the framework to set-systems and uniform hypergraphs, with seminal contributions from Katona, Frankl, and Lovász. Spectral generalizations link to work by Hoffman, Nikiforov, and Wilf, while algorithmic and probabilistic variants connect Turán-type bounds to research by Janson, Luczak, and Ruciński.

Applications and examples

Turán's theorem appears in proofs and constructions across combinatorics, theoretical computer science, and discrete geometry. It is used to bound edge densities in Ramsey-type problems studied by Frank P. Ramsey and Erdős–Szekeres-style combinatorial geometry, informs analyses of property testing and subgraph-freeness algorithms in theoretical work associated with Alon, Goldreich, and Szemerédi, and yields constraints in extremal set theory that interact with the Erdős–Ko–Rado theorem. Concrete examples include bounding edges in triangle-free social network models examined alongside probabilistic models by Erdős and Rényi, constructing instances for hardness reductions in complexity theory referenced in work related to Stephen Cook and Richard Karp, and serving as a benchmark in extremal examples used by Komlós, Szemerédi, and T. S. Michael.

Category:Theorems in graph theory