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.
- D. Christofides, P. Keevash, D. Kühn and D. Osthus. Finding Hamilton cycles in robustly expanding digraphs Preprint.
- D. Christofides, P. Keevash, D. Kühn and D. Osthus. A semi-exact degree condition for Hamilton cycles in digraphs Preprint.
- C. Grosu and J. Hladký. The extremal function for partial bipartite tilings Preprint.
- P. Allen, J. Böttcher and J. Hladký. Filling the gap between Turán's theorem and Pósa's conjecture Preprint.
- P. Allen. Dense H-free graphs are almost (χ(H)-1)-partite. Electronic Journal of Combinatorics, 17(1): R21, 2010.
- P. Allen. Covering Two-Edge-Coloured Complete Graphs with Two Disjoint Monochromatic Cycles. Combinatorics, Probability & Computing, 17(4): 471 - 486, 2008.
- P. Allen. Minimum degree conditions for cycles. Preprint.
- Noga Alon, A. Coja-Oghlan, Hiep Han, Mihyun Kang, Vojtech Rodl, Mathias Schacht. Quasi-randomess and algorithmic regularity for graphs with general degree distributions. SIAM J. on Computing, to appear.