pith. sign in

arxiv: 2604.11633 · v1 · submitted 2026-04-13 · 🧮 math.CO

Edge disjoint Hamilton cycles in random digraphs of constant minimum degree

Colin Cooper , Alan Frieze This is my paper

Pith reviewed 2026-05-10 15:44 UTC · model grok-4.3

classification 🧮 math.CO MSC 05C8005C45
keywords random digraphsHamilton cyclesedge-disjoint cyclesminimum degreedirected graphsprobabilistic method
0
0 comments X

The pith

Random digraphs conditioned on minimum in- and out-degree at least k+1 contain k edge-disjoint Hamilton cycles with high probability.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper shows that a random directed graph on n vertices with cn edges, when conditioned to have every vertex with in-degree and out-degree at least k+1, almost surely contains k edge-disjoint directed cycles that each pass through every vertex exactly once. Hamilton cycles are basic objects for routing problems in directed networks, and edge-disjoint copies allow the network to support multiple independent traversals without sharing edges. The result requires only a constant average degree, provided that constant is large enough depending on the fixed integer k. This extends earlier existence results for single Hamilton cycles to multiple disjoint ones under a uniform degree floor.

Core claim

We study the existence of directed Hamilton cycles in random digraphs with m edges where we condition on minimum in- and out-degree δ ≥ k+1, where k ≥ 1. Denote such a random graph by D_{n,m}^{(δ≥k+1)}. Let m=cn and c≥ c_k, where c_k is a sufficiently large constant. We prove that w.h.p. D_{n,m}^{(δ≥k+1)} contains k edge disjoint Hamilton cycles.

What carries the argument

The random digraph D_{n,m}^{(δ≥k+1)} obtained by conditioning the uniform model on m=cn edges to have minimum in- and out-degree at least k+1, which is shown to contain k edge-disjoint Hamilton cycles.

If this is right

  • For every fixed k the conditioned digraph is k-edge-Hamiltonian with high probability.
  • The minimum-degree conditioning suffices to guarantee the disjoint cycles once the total edge count reaches a large enough linear multiple of n.
  • The same conclusion applies uniformly for all k as long as c is chosen larger than the corresponding c_k.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Similar conditioning arguments might produce multiple disjoint Hamilton cycles in other sparse directed random models beyond the uniform edge model.
  • The precise growth rate of the threshold c_k with k remains open and could be studied by refining the probabilistic embedding techniques.

Load-bearing premise

That the average degree c must exceed a sufficiently large threshold c_k that depends on k.

What would settle it

An explicit sequence of digraphs with cn edges for arbitrarily large c, minimum in- and out-degrees at least k+1, but containing fewer than k edge-disjoint Hamilton cycles.

Figures

Figures reproduced from arXiv: 2604.11633 by Alan Frieze, Colin Cooper.

Figure 1
Figure 1. Figure 1: Original and rearranged path sections showing the permutations [PITH_FULL_IMAGE:figures/full_fig_p019_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Left: Original cycle (P1, P2, P3) with permutation ϕ = (1, 3, 2). Broken edges shown dotted. Right: New cycle (P1, P3, P2) with associated permutations τ = (1, 3, 2) and λ = (1, 2, 3). Permutations given in cycle notation. Let H stand for the union of the permutation digraph C ∗ i and E4,i. We finish our proof by proving Lemma 13. P(H does not contain a Hamilton cycle) = o(1). 19 [PITH_FULL_IMAGE:figures/… view at source ↗
read the original abstract

We study the existence of directed Hamilton cycles in random digraphs with $m$ edges where we condition on minimum in- and out-degree $\d \ge k+1$, where $k \ge 1$. Denote such a random graph by $D_{n,m}^{(\delta\geq k+1)}$. Let $m=cn$ and $c\ge c_k$, where $c_k$ is a sufficiently large constant. We prove that w.h.p. $D_{n,m}^{(\delta\geq k+1)}$ contains $k$ edge disjoint Hamilton cycles.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The manuscript proves that for any fixed k ≥ 1 and m = c n with c ≥ c_k sufficiently large, the random digraph D_{n,m} conditioned on minimum in- and out-degree at least k+1 contains k edge-disjoint directed Hamilton cycles with high probability.

Significance. If the argument holds, the result extends Hamiltonicity results from undirected random graphs and unconditioned digraphs to the sparse directed setting with explicit minimum-degree conditioning. It relies on a standard rotation-extension technique adapted to digraphs together with the conditioned configuration model, yielding a self-contained probabilistic proof that strengthens the understanding of cycle packings in random digraphs.

minor comments (2)
  1. The dependence of c_k on k is stated to exist but the explicit form or growth rate is not derived; adding a brief remark on how c_k arises from the expansion parameters would improve readability.
  2. Notation for the remaining graph after removing one Hamilton cycle (e.g., the updated degree sequence) could be introduced earlier to ease following the iterative argument.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their careful reading of our manuscript and for the positive assessment of its significance. The referee's summary accurately reflects the main theorem: that for any fixed k ≥ 1 and sufficiently large c = c_k, the random digraph D_{n,m} conditioned on minimum in- and out-degree at least k+1 contains k edge-disjoint directed Hamilton cycles with high probability. We are pleased that the referee views the adaptation of the rotation-extension technique to the conditioned configuration model as a self-contained contribution. Since the report lists no major comments, we have no point-by-point responses to provide at this stage. We remain available to address any minor suggestions or clarifications that may arise during the revision process.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The manuscript establishes the existence of k edge-disjoint Hamilton cycles in the conditioned random digraph model D_{n,m}^{(δ≥k+1)} via the rotation-extension technique applied to the configuration model, with iterative removal of cycles while preserving expansion and degree properties. All steps rely on standard probabilistic arguments and direct analysis of the random model without any reduction of a claimed result to a fitted parameter, self-definition, or load-bearing self-citation chain. The derivation is self-contained against the model definition and does not rename or smuggle prior results as new derivations.

Axiom & Free-Parameter Ledger

1 free parameters · 1 axioms · 0 invented entities

The claim rests on standard probabilistic combinatorics tools and an unspecified threshold constant c_k; no new entities are introduced.

free parameters (1)
  • c_k
    Sufficiently large constant (depending on k) that sets the edge density threshold m = c n; its explicit value is not given.
axioms (1)
  • standard math Standard concentration inequalities and the probabilistic method for random graphs
    Used implicitly to establish 'w.h.p.' properties under the degree conditioning.

pith-pipeline@v0.9.0 · 5381 in / 1206 out tokens · 34754 ms · 2026-05-10T15:44:07.369080+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

18 extracted references · 18 canonical work pages

  1. [1]

    Anastos, Packing Hamilton cycles in cores of random graphs, arxiv2107.03527

    M. Anastos, Packing Hamilton cycles in cores of random graphs, arxiv2107.03527

    work page arXiv

  2. [2]

    Anastos and A.M

    M. Anastos and A.M. Frieze, Hamilton cycles in random graphs with minimum degree at least 3: an improved analysis,Random Structures and Algorithms57 (2020) 865-878

    work page 2020

  3. [3]

    Aronson, A.M

    J. Aronson, A.M. Frieze and B. Pittel, Maximum matchings in sparse random graphs: Karp-Sipser revisited,Random Structures and Algorithms12 (1998) 111-178

    work page 1998

  4. [4]

    Bollob´ as, A probabilistic proof of an asymptotic formula for the number of labelled regular graphs,European Journal on Combinatorics1 (1980) 311-316

    B. Bollob´ as, A probabilistic proof of an asymptotic formula for the number of labelled regular graphs,European Journal on Combinatorics1 (1980) 311-316. 22

    work page 1980

  5. [5]

    Bollob´ as, C

    B. Bollob´ as, C. Cooper, T. Fenner and A.M. Frieze, On Hamilton cycles in sparse random graphs with minimum degree at leastk,Journal of Graph Theory34 (2000) 42-59

    work page 2000

  6. [6]

    Cooper and A.M

    C. Cooper and A.M. Frieze, Hamilton cycles in a class of random directed graphs, Journal of Combinatorial TheoryB 62 (1994) 151-163

    work page 1994

  7. [7]

    Cooper and A.M

    C. Cooper and A.M. Frieze, Hamilton cycles in random digraphs with minimum degree at least one,SIAM Journal on Discrete Mathematics39 (2025)

    work page 2025

  8. [8]

    Durrett, Probability: Theory and Examples, 4th Edition,Cambridge University Press2010

    R. Durrett, Probability: Theory and Examples, 4th Edition,Cambridge University Press2010

    work page

  9. [9]

    Dyer and A.M

    M.E. Dyer and A.M. Frieze,On patching algorithms for random asymmetric traveling salesman problems, Mathematical Programming 46 (1990) 361–378

    work page 1990

  10. [10]

    Frieze, An algorithm for finding hamilton cycles in random digraphs,Journal of Algorithms9 (1988) 181-204

    A.M. Frieze, An algorithm for finding hamilton cycles in random digraphs,Journal of Algorithms9 (1988) 181-204

    work page 1988

  11. [11]

    Frieze and M

    A.M. Frieze and M. Karo´ nski, Introduction to Random Graphs, Cambridge University Press, 2015

    work page 2015

  12. [12]

    Frieze, R.M

    A.M. Frieze, R.M. Karp and B. Reed,When is the assignment bound asymptotically tight for the asymmetric traveling-salesman problem?, SIAM Journal on Computing 24 (1995) 484–493

    work page 1995

  13. [13]

    Frieze and B

    A.M. Frieze and B. Pittel, Perfect matchings in random graphs with prescribed minimal degree,Trends in Mathematics, Birkhauser Verlag, Basel(2004) 95-132

    work page 2004

  14. [14]

    Frieze and G

    A.M. Frieze and G. Sorkin, The probabilistic relationship between the assignment and asymmetric traveling salesman problems,SIAM Journal on Computing36 (2007) 1435- 1452

    work page 2007

  15. [15]

    Karp,A patching algorithm for the non-symmetric traveling salesman problem, SIAM Journal on Computing 8 (1979) 561–573

    R.M. Karp,A patching algorithm for the non-symmetric traveling salesman problem, SIAM Journal on Computing 8 (1979) 561–573

    work page 1979

  16. [16]

    D. E. Knuth, R. Motwani and B. Pittel,Stable husbands, Random Structures and Al- gorithms1, (1990) 1-14

    work page 1990

  17. [17]

    McDiarmid, Clutter percolation and random graphs,Mathematical Programming Studies13 (1980) 17-25

    C. McDiarmid, Clutter percolation and random graphs,Mathematical Programming Studies13 (1980) 17-25

    work page 1980

  18. [18]

    Robinson and N

    R. Robinson and N. Wormald, Almost all cubic graphs are Hamiltonian,Random Struc- tures and Algorithms3 (1992) 117-125. 23

    work page 1992