Skip to main content Skip to navigation

Extremal Graph Theory

The basic aim of extremal graph theory is to show that a graph with sufficiently many edges must contain as a subgraph some desired structure. Perhaps the most fundamental theorem is Turán's theorem: an n-vertex complete balanced k-partite graph does not contain Kk+1 , but every n-vertex graph with more edges must contain Kk+1. A generalisation, the Erdős-Stone theorem, states that o(n2) more edges guarantees the presence of any fixed subgraph of chromatic number k+1.

Another basic theorem is Dirac's theorem: every n-vertex graph all of whose vertices have degree at least n/2 has a Hamilton cycle. Such a minimum degree condition is more appropriate when one desires a large or spanning subgraph; it avoids the possibility of a few isolated vertices destroying the desired property. Recent generalisations, using the Szemerédi Regularity Lemma and the Blow-up Lemma, show that a large graph with minimum degree kn /(k+1) contains the kth power of a Hamilton cycle (due to Komlós, Sárközy and Szemerédi) and an o(n) greater minimum degree forces the existence of any bounded-degree graph with chromatic number k+1 and small bandwidth (due to Böttcher, Schacht and Taraz).

A recent area of study is which conditions force the existence of intermediate-sized subgraphs - usually one must insist on stronger conditions than are required to force fixed-size subgraphs, but weaker conditions than those which force spanning subgraphs. The best possible relationship is often non-trivial.

An interesting branch of extremal graph theory is Ramsey theory: this is the study of graph properties which are forced not by insisting on many edges but simply by asking for enough vertices. The basic theorem - Ramsey's theorem - states that for any k, any graph with R(k) vertices contains either a clique or independent set on k vertices. Only quite poor bounds - essentially 2k/2<R(k)<4k - are known; finding better bounds is a major problem.

Problems in Ramsey theory are usually expressed in terms of edge-coloured complete graphs: so Ramsey's theorem guarantees a monochromatic Kk in any two-edge-coloured R(k)-vertex complete graph. In these terms, we can define R(H1,H2) to be the smallest number of vertices which guarantees that any two-edge-coloured complete graph contains either H1 in the first colour or H2 in the second. Even this quantity is known only for a few very simple classes of graphs: when, as with traditional extremal graph theory, chromatic number plays an important role.

Sample publications: