Hamilton decompositions of regular expanders: applications

In a recent paper, we showed that every sufficiently large regular digraph G on n vertices whose degree is linear in n and which is a robust outexpander has a decomposition into edge-disjoint Hamilton cycles. The main consequence of this theorem is that every regular tournament on n vertices can be decomposed into (n−1)/2(n−1)/2 edge-disjoint Hamilton cycles, whenever n is sufficiently large. This verified a conjecture of Kelly from 1968. In this paper, we derive a number of further consequences of our result on robust outexpanders, the main ones are the following:
(i) an undirected analogue of our result on robust outexpanders;
(ii) best possible bounds on the size of an optimal packing of edge-disjoint Hamilton cycles in a graph of minimum degree δ for a large range of values for δ.
(iii) a similar result for digraphs of given minimum semidegree;
(iv) an approximate version of a conjecture of Nash-Williams on Hamilton decompositions of dense regular graphs;
(v) a verification of the ‘very dense’ case of a conjecture of Frieze and Krivelevich on packing edge-disjoint Hamilton cycles in random graphs;
(vi) a proof of a conjecture of Erdős on the size of an optimal packing of edge-disjoint Hamilton cycles in a random tournament.