Hamilton cycles and algorithms

We present three results in graph theory, united by the themes of Hamilton cycles and algorithms. A Hamilton cycle in a graph is a cycle that contains every vertex of the graph.
The first result concerns path decompositions of digraphs, specifically an extension of a conjecture due to Alspach, Mason, and Pullman. There is a natural lower bound for the number paths needed in an edge decomposition of a directed graph in terms of its degree sequence. We show that this bound is asymptotically almost surely correct for the random directed graph for a large range of p.
We also give a polynomial-time algorithm for detecting almost Hamilton cycles in dense regular graphs. If such a cycle exists, we give a (randomized) polynomial-time algorithm to find it. The problem becomes NP-complete if we drop either the density or the regularity condition. The algorithm uses spectral partitioning to construct a robust expander decomposition, a structure introduced by Kühn and Osthus, as well as some further algorithmic ingredients.
Lastly, we consider switch-based Markov chains for the approximate uniform sampling of Hamilton cycles in graphs of high minimum degree. As our main result, we show that every pair of Hamilton cycles in a graph with minimum degree at least n/2+7 can be transformed into each other by 10-switches. Using a strengthening of this result, we prove that the 10-switch Markov chain is rapidly mixing (i.e. converges quickly to its stationary distribution) on the class of dense monotone graphs.