Minimum degree edge-disjoint Hamilton cycles in random directed graphs

2025/02/03 by Ferber, Asaf, Mond, Adva
#05C38 #05C45 #05C80 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2502.01631

Abstract

In this paper we consider the problem of finding ``as many edge-disjoint Hamilton cycles as possible'' in the binomial random digraph D<sub>n,p</sub>. We show that a typical D<sub>n,p</sub> contains precisely the minimum between the minimum out- and in-degrees many edge-disjoint Hamilton cycles, given that p≥ log<sup>15</sup> n/n, which is optimal up to a factor of polylog n. Our proof provides a randomized algorithm to generate the cycles and uses a novel idea of generating D<sub>n,p</sub> in a sophisticated way that enables us to control some key properties, and on an ``online sprinkling'' idea as was introduced by Ferber and Vu.

Related

• Hamilton cycles in random digraphs with minimum degree at least one
• Covering Random Digraphs with Hamilton Cycles
• Packing, Counting and Covering Hamilton cycles in random directed graphs
• Packing and counting arbitrary Hamilton cycles in random digraphs
• Random directed graphs are robustly Hamiltonian