Extremal Graph Theory
Extremal graph theory asks how large or dense a graph can be while avoiding a prescribed substructure, and identifies the extremal configurations.
Definition
The study of the maximum or minimum value of a graph parameter, such as the number of edges, subject to a structural constraint such as the absence of a fixed subgraph.
Scope
This topic centers on Turan-type problems - the maximum number of edges in a graph with no given subgraph - beginning with Mantel's and Turan's theorems and extending to the Erdos-Stone theorem, which determines the asymptotic extremal density for any forbidden subgraph. It introduces the interplay of density, structure, and the Szemeredi regularity method.
Core questions
- What is the maximum number of edges in a graph on n vertices that contains no copy of a given subgraph?
- Which graphs achieve these extremal bounds?
- How does the chromatic number of a forbidden subgraph govern the asymptotic answer?
- How do regularity methods reduce dense graphs to bounded structure?
Key concepts
- Forbidden subgraphs
- Turan graph
- Mantel's theorem
- Extremal number (Turan number)
- Erdos-Stone theorem
- Szemeredi regularity lemma
Key theories
- Turan's theorem
- Among all graphs on n vertices with no complete subgraph on r+1 vertices, the balanced complete r-partite graph has the most edges, generalizing Mantel's triangle-free bound and anchoring extremal graph theory.
- Erdos-Stone theorem
- For any fixed forbidden subgraph H, the maximum edge density of an H-free graph is asymptotically determined by the chromatic number of H, unifying Turan-type extremal results.
Clinical relevance
Extremal density results bound the structure of large networks and constraint systems, and the regularity method developed within this area has applications in property testing, theoretical computer science, and additive combinatorics.
History
Mantel's 1907 triangle-free bound and Turan's 1941 generalization launched the field; the Erdos-Stone-Simonovits theory and Szemeredi's regularity lemma made it a central pillar of modern combinatorics.
Key figures
- Paul Turan
- Paul Erdos
- Endre Szemeredi
Related topics
Seminal works
- bollobas1998
- diestel2017
Frequently asked questions
- What is a Turan-type problem?
- It asks for the largest number of edges a graph can have while avoiding a fixed subgraph; the canonical example is the maximum edges in a triangle-free graph.
- How does extremal graph theory relate to Ramsey theory?
- Both study unavoidable structure, but extremal theory fixes a forbidden subgraph and maximizes edges, whereas Ramsey theory guarantees a monochromatic structure once the graph is large enough.