# 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 *K _{k+1}* , but every

*n*-vertex graph with more edges must contain

*K*. A generalisation, the Erdős-Stone theorem, states that

_{k+1}*o(n*more edges guarantees the presence of any fixed subgraph of chromatic number

^{2})*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*to be the smallest number of vertices which guarantees that any two-edge-coloured complete graph contains either

_{1},H_{2})*H*in the first colour or

_{1}*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.

_{2}## 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.*