Extremal graph theory

Summary

Extremal graph theory studies how large or small a graph can be when it must have, or must avoid, a given structure. Its basic quantity is the extremal number $\mathrm{ex}(n, H)$, the largest number of edges of a graph on $n$ vertices with no subgraph isomorphic to $H$. Turán's theorem computes it for complete graphs, and the Erdős–Stone theorem gives it asymptotically for every non-bipartite $H$. For bipartite $H$ the question leads to the Zarankiewicz problem, which is still largely open.