Hamilton decompositions of regular expanders: applications

Abstract

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 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 d for a large range of values for d. (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) the observation that dense quasi-random graphs are robust outexpanders; (vi) a verification of the `very dense' case of a conjecture of Frieze and Krivelevich on packing edge-disjoint Hamilton cycles in random graphs; (vii) a proof of a conjecture of Erdos on the size of an optimal packing of edge-disjoint Hamilton cycles in a random tournament.

final version, to appear in J. Combinatorial Theory B

References in corpus (5)

• On the resilience of Hamiltonicity and optimal packing of Hamilton cycles in random graphs
• Proof of the 1-factorization and Hamilton decomposition conjectures II: the bipartite case
• Proof of the 1-factorization and Hamilton decomposition conjectures III: approximate decompositions
• Proof of the 1-factorization and Hamilton decomposition conjectures IV: exceptional systems for the two cliques case
• Hamilton decompositions of regular tournaments

Cited by in corpus (19)

• Hamilton cycles in graphs and hypergraphs: an extremal perspective
• Proof of a conjecture of Thomassen on Hamilton cycles in highly connected tournaments
• Optimal path and cycle decompositions of dense quasirandom graphs
• Proof of Komlós's conjecture on Hamiltonian subsets
• Hamilton Cycles in Random Graphs: a bibliography
• The robust component structure of dense regular graphs and applications
• Proof of the 1-factorization and Hamilton decomposition conjectures II: the bipartite case
• Edge-disjoint Hamilton cycles in random graphs
• Packing a randomly edge-colored random graph with rainbow $k$-outs
• Path and cycle decompositions of dense graphs
• A blow-up lemma for approximate decompositions
• Packing, Counting and Covering Hamilton cycles in random directed graphs
• Decomposing tournaments into paths
• On prisms, Möbius ladders and the cycle space of dense graphs
• Optimal covers with Hamilton cycles in random graphs
• Packing and counting arbitrary Hamilton cycles in random digraphs
• Path decompositions of tournaments
• Counting and packing Hamilton cycles in dense graphs and oriented graphs
• Approximate Hamilton decompositions of robustly expanding regular digraphs