- The paper proves that, for any k ≥ 1 and sufficient edge density, sparse random digraphs with minimum degree k+1 w.h.p. contain k edge-disjoint Hamilton cycles.
- The approach employs a phase-based algorithmic construction that starts with edge-disjoint perfect matchings, aggregates cycle covers, and patches them into Hamilton cycles.
- The results sharpen the degree-threshold conditions for Hamiltonicity and advance techniques for analyzing connectivity and resilience in directed networks.
Edge-Disjoint Hamilton Cycles in Sparse Random Digraphs of Constant Minimum Degree
Problem Statement and Main Result
This paper investigates the packing of edge-disjoint Hamilton cycles in sparse random directed graphs with controlled minimum in- and out-degree. Specifically, for k≥1 and edge density m=cn where c≥ck​ for some absolute constant ck​=O(1), the focus is on the random digraph Dn,m(δ≥k+1)​—that is, the uniform random digraph on n vertices with m edges, conditioned on all in-degrees and out-degrees being at least k+1. The authors prove that, with high probability (w.h.p.), such a digraph contains k edge-disjoint Hamilton cycles.
Formally, for every k≥1 there exists m=cn0 such that if m=cn1, the random digraph m=cn2 w.h.p. contains m=cn3 edge-disjoint Hamilton cycles.
Context and Relation to Prior Work
The existence of Hamilton cycles in random directed graphs (digraphs) and their undirected analogues has been extensively studied. Early results by McDiarmid established threshold edge densities for Hamiltonicity in m=cn4 [see e.g. McDiarmid (1980)]. Frieze later precisely characterized the limiting probability for Hamiltonicity in the unconditioned random digraph [F1]. Conditioning on minimum degree is known to be both necessary and sufficient for Hamiltonicity at certain densities; recent advances have resolved similar questions in undirected random graphs conditioned on minimum degree [Anastos 2021, AF2].
Edge-disjoint Hamilton cycle packing in random graphs is a highly nontrivial extension of finding a single Hamilton cycle, and the degree constraints become substantially more complex. This paper extends the probabilistic analysis for Hamilton decomposition in the directed case, using tools that have been developed for undirected graphs but adapting them to the substantially more intricate random directed configuration spaces.
Model and Probabilistic Framework
The random digraph is constructed via a configuration or pairing model: edges are specified via a random sequence of ordered vertex pairs, conditioned so that every vertex has both in-degree and out-degree at least m=cn5. This is realized through independent, truncated Poisson distributions for in- and out-degrees, further conditioned on the sum of degrees being exactly m=cn6.
The authors show that, with linear (m=cn7) total edge count and large enough m=cn8, the probability of creating loops and parallel edges vanishes, so the resulting random multi-digraph is simple with constant probability. Properties that hold w.h.p. in the truncated Poisson model thus carry over to the simple digraph case.
Proof Structure
The proof is algorithmic and divided into structured probabilistic phases:
Phase 1: Construction of Edge-Disjoint Cycle Covers
The first goal is to create m=cn9 edge-disjoint perfect matchings in the associated bipartite graphs, corresponding to c≥ck​0 edge-disjoint permutation digraphs (i.e., c≥ck​1 cycle covers of the vertices with vertex-disjoint directed cycles using disjoint edge sets). The classical Hall-type expansion condition is shown to hold w.h.p. by estimating the probability of small sets failing to expand, using Chernoff bounds and unions over small sets. Each perfect matching is constructed with a randomized greedy algorithm, employing additional random edges as "boosters" to repair sets lacking perfect matchings. These cycle covers are shown to have c≥ck​2 cycles w.h.p.
Phase 2: Aggregation into Long Cycles
Cycle covers are improved so that all cycles are of length at least c≥ck​3. This phase uses random walks and patching moves, leveraging additional random edges to merge small cycles with longer paths. A careful two-phase tree exploration process is used: "Out-Phase" extends paths from small cycles, while "In-Phase" attempts to close these extended paths into long cycles. The authors analyze the expansion of these exploration trees and show that short cycles can be eliminated with high probability after a bounded number of attempts, relying critically on expansion and the abundance of random edges.
Phase 3: Patching Cycle Covers to Hamilton Cycles
With each edge-disjoint cover containing only long cycles, a final patching phase completes the cycles into Hamilton cycles. The cycles are broken into path sections at carefully chosen breakpoints (with sufficient separation ensured via probabilistic estimates), and a second moment argument is used to show that, with the remaining random edges, it is possible to reconnect the paths into a single directed cycle, i.e., a Hamilton cycle. Dependence between possible reconstructions is carefully controlled via combinatorial enumeration and permutation group symmetries.
Strong and Contradictory Claims
The main technical claim is that c≥ck​4 edge-disjoint Hamilton cycles appear w.h.p. in c≥ck​5 for linear c≥ck​6 and sufficiently large constant c≥ck​7 relative to c≥ck​8, which matches natural degree-based lower bounds. This establishes, in the sparse (linear edge) regime, the tightness of minimum degree thresholds for Hamilton packing in random digraphs, strengthening the analogy with undirected results.
Additionally, the authors emphasize that the constructed cycle covers and subsequent Hamilton cycles use disjoint edge sets, addressing the significantly more difficult packing problem rather than just existence. All results are shown to be robust under conditioning on simple graphs (no loops or parallel edges), due to the high-probability structure of the underlying configuration model.
Implications and Further Directions
This work sharpens the probabilistic understanding of Hamilton cycle packing in random digraphs with prescribed degree constraints. The algorithmic decomposition and probabilistic phase analysis provide tools for evaluating resilience and expandability in random networks. Practically, such results inform the design and analysis of fault-tolerant communication protocols, coding schemes, and randomized constructions in combinatorial optimization.
On the theoretical side, the methods developed suggest possible refinements for mixed settings (e.g., random regular digraphs, digraphs with varying degree sequences, or graphs with additional structural constraints) and could guide analogous progress for perfect c≥ck​9-cycle packings or other spanning structures in random graphs.
Further research directions may include:
- Tightening the constants ck​=O(1)0 for optimality.
- Extending the analysis to more general degree sequences or other random graph models.
- Algorithmic implications: finding explicit polynomial-time algorithms for extracting such Hamilton decompositions in random digraphs.
Conclusion
The paper establishes that a sparse random digraph with linear edge density and minimum in- and out-degree at least ck​=O(1)1 contains ck​=O(1)2 edge-disjoint Hamilton cycles w.h.p., for any fixed ck​=O(1)3, provided the density constant ck​=O(1)4 exceeds an explicit threshold. The approach combines probabilistic, combinatorial, and algorithmic tools, employing phase-based construction, expansion arguments, and second moment calculations. The results provide a sharpening of degree-threshold phenomena for Hamiltonicity and Hamilton decomposition in the random directed setting, complementing and advancing the foundational work on undirected random graphs.
