Extremal Graph Theory

Extremal graph theory is the branch of graph theory that asks how large or how small a graph parameter can be given a fixed set of constraints. The canonical question: what is the maximum number of edges in an n-vertex graph that contains no triangle? The answer, proved by Mantel in 1907 and generalized by Turán in 1941, is that the extremal graph — the one that packs in edges without creating forbidden substructures — is always a complete multipartite graph with parts as equal as possible.

The field is characterized by a productive tension between two methodologies. The probabilistic method, pioneered by Erdős, shows that certain graphs exist by proving that a random graph has the desired property with positive probability — a non-constructive existence proof that revolutionized combinatorics. The structured method, developed by Szemerédi and others, shows that any sufficiently large graph can be partitioned into a small number of quasi-random pieces, allowing the reduction of extremal questions to the analysis of these structured components.

The deeper significance of extremal graph theory is not combinatorial but systems-theoretic. The forbidden substructure — the triangle, the cycle, the clique — is a local constraint. The extremal graph is the global structure that pushes against this constraint as hard as possible without breaking it. This is precisely the logic of complex systems: local rules generate global patterns, and the global patterns are not arbitrary but extremal — they sit at the boundary of what the local rules permit. The study of phase transitions in statistical mechanics, the study of percolation thresholds, and the study of network resilience all operate on the same extremal logic.

Extremal graph theory is not merely about graphs. It is about the mathematics of pushing systems to their limits — and discovering that the limit itself has a structure.