Hamilton Decompositions of Graphs - School of Mathematics graduate mug

Hamilton Decomposition A Hamilton path of a graph is a path containing every vertex of the graph, and a Hamilton cycle is a cycle containing every vertex of the graph. Hamilton paths and cycles are central objects of study in graph theory, and they have many applications in computer science. A Hamilton decomposition of a graph is a partition of the edges of the graph into Hamilton cycles. For example, a Hamilton decomposition of the small rhombicosidodecahedron is shown above (with one cycle in red and the other in black).

WaleckiWalecki's theorem (1892) says that the complete graph Kn on n vertices has a Hamilton decomposition whenever n is odd. (If n is even, then each vertex of Kn has odd degree and so clearly no such decomposition exists.) His argument is based around a simple decomposition of Kn-1 into Hamilton paths, shown to the right for K8. The remaining vertex is then used to join the paths up into cycles.

It is natural to try and generalise this result to oriented graphs, i.e. graphs where every edge now has an orientation. Here we consider directed cycles, so all the edges are oriented consistently. A Hamilton decomposition of an oriented graph is a partition of the edges of the graph into directed Hamilton cycles. It is simple to turn Kn into a oriented graph - we just arbitrarily assign an orientation to each edge, and the resulting graph is called a tournament.

In the undirected case, it was obvious that for Kn to have a Hamilton decomposition, its vertices needed to have even degree. In the directed case, we need more - every vertex needs to have the same number of edges going in as it has coming out. We say that tournaments satisfying this requirement are regular. 

Hamilton Turnier A famous conjecture of Kelly from 1968 states that every regular tournament has a Hamilton decomposition. This seemingly simple problem has been very resistant to attack, and was solved for large tournaments in 2012 by Birmingham mathematicians Daniela Kühn and Deryk Osthus in a proof spanning over 90 pages.

This is part of a successful and ongoing research programme involving collaborations with Demetres Christofides, Bela Csaba, Dan Hefetz, Peter Keevash, Luke Kelly, Fiachra Knox, John Lapinskas, Allan Lo, Richard Mycroft, Katherine Staden and Andrew Treglown.

In fact, Kühn and Osthus proved a significantly more general result - they showed that every robust expander has a Hamilton decomposition. Such graphs arise in a variety of settings. For example, any large regular graph on n vertices whose degree is slightly larger than n/2 is a robust expander, and therefore has a Hamilton decomposition by their result. This increased generality means that their result also resolves several other long-standing conjectures.

Even more, the result doesn't just show that a decomposition exists - it provides a polynomial time algorithm for finding it. This can be applied to the travelling salesman problem, which asks for a shortest tour visiting all vertices in a weighted graph or directed graph.

The problem itself is NP-complete and thus probably cannot be solved in polynomial time. But we can still ask for heuristic solutions which are guaranteed to give "good answers". Imagine putting all the possible solutions in an ordered list from lowest weight to highest weight.

Until recently, the best one could do in polynomial time for a (directed) graph on n vertices was to give an answer guaranteed not to be in the bottom (1/n)th part of the list! The result of Kühn and Osthus can be applied to give an answer guaranteed to be in (roughly) the top half.