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 K_k+1 , but every n-vertex graph with more edges must contain K_k+1. A generalisation, the Erdős-Stone theorem, states that o(n²) 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 k^th 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 2^k/2<R(k)<4^k - 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 K_k in any two-edge-coloured R(k)-vertex complete graph. In these terms, we can define R(H₁,H₂) to be the smallest number of vertices which guarantees that any two-edge-coloured complete graph contains either H₁ in the first colour or H₂ 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:

• 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.
  

• D. Christofides, D. Kühn and D. Osthus. Edge-disjoint Hamilton cycles in graphs Preprint.
  

• J. Böttcher, D. Piguet and J. Hladký. The tripartite Ramsey number for trees Preprint.
  

• J. Hladký, D. Kral' and S. Norine. Counting flags in triangle-free 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.