{"id":"f71f8186-59a0-44a8-8c08-bee49acb14e6","arxiv_id":"2502.01631","paper_version":1,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"For p ≥ log^15 n / n, the random digraph D_{n,p} almost surely contains exactly δ±(D_{n,p}) edge-disjoint Hamilton cycles.","lead":"This paper proves that a random directed graph typically contains as many edge-disjoint Hamilton cycles as its minimum in/out degree, for all edge probabilities down to log^15 n / n. It closes a gap in a long line of work on random directed graphs and provides a randomized algorithm that finds the cycles.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Stated p1 makes np1 = sqrt(np) log^2 n, which is not o(sqrt(np)/log n); Lemma 3.5's gap claim is asymptotically false, so the Phase 1 Gale-Ryser argument is unsupported as written.","rationale":"The reader's weakest assumption correctly identified the degree-gap survival after the second exposure as the most fragile point. My stress-test pass sharpens that concern into a concrete algebraic error: the printed parameter p1 is too large by a factor log^4 n for Lemma 3.5's asymptotic comparison to hold. Since Lemma 3.5 is what guarantees delta = delta^pm(D_{n,p}) and identifies x as the unique minimum-degree vertex in the final bipartite graph B, and since Claim 3.7's Gale-Ryser verification needs gamma = delta2(B) - delta(B) to be large, the Phase 1 construction is not securely proved with the stated parameters. The error is not merely stylistic: the same p1 also contradicts the q = p1/log^2 n relation used in the final coupling argument. If the intended definition is p1 = sqrt(p/(n log^4 n)), then the proof likely goes through because np1 becomes sqrt(np)/log^2 n, making sqrt(np0)/log n = omega(np1), and q = p1/log^2 n matches Lemma 4.2. Thus the concern is load-bearing but repairable; it should be resolved before the theorem is accepted. I therefore move the verdict from ACCEPT to CONDITIONAL, pending a corrected parameter definition and a recheck of Lemma 3.5 and Claim 3.7. No issue with the authorial work is implied; this is a technical verification matter in a long and intricate proof.","tokens_in":33453,"tokens_out":13349,"duration_ms":106177,"concrete_test":"Substitute the printed p1 = sqrt(p log^4 n / n) into the two key equations: (i) in Lemma 3.5, compute np1 = sqrt(np) log^2 n and sqrt(np0)/log n = Theta(sqrt(np)/log n); verify the claimed omega relation fails by a factor log^3 n. (ii) Check q = p1/log^2 n against Lemma 4.2's q = sqrt(p/(n log^8 n)): with the printed p1, q = sqrt(p/n), a mismatch by log^4 n. If both tests fail, change p1 to sqrt(p/(n log^4 n)) and re-run the two computations. Under the corrected p1, np1 = sqrt(np)/log^2 n and q = p1/log^2 n = sqrt(p/(n log^8 n)), so the gap survives and the coupling estimate in Lemma 5.5 aligns.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The paper defines p1 = sqrt(p log^4 n / n) in Procedure 1, so np1 = n * sqrt(p log^4 n / n) = sqrt(np) log^2 n. Lemma 3.5 requires sqrt(np0)/log n = omega(np1) to ensure the unique minimum-degree vertex in B' stays the unique minimum after the second exposure. But sqrt(np0)/log n = Theta(sqrt(np)/log n), and the ratio (sqrt(np)/log n) / (sqrt(np) log^2 n) = 1/log^3 n = o(1). Thus the displayed chain 'sqrt(np)/(sqrt(2) log n) = omega(sqrt(np)/log^2 n) = omega(np1)' is false: the last equality would need np1 = o(sqrt(np)/log^2 n), whereas the printed p1 gives np1 = sqrt(np) log^2 n. This invalidates the proof of Lemma 3.5. Consequently, Lemma 3.6 and Claim 3.7 rely on gamma = delta2(B) - delta(B) being positive and large; if gamma = 0, the union bounds in the five cases of Claim 3.7 fail. The parameter inconsistency is confirmed by Section 5.3, which sets q = p1/log^2 n but Lemma 4.2 uses q = sqrt(p/(n log^8 n)). With the printed p1, q = sqrt(p/n), not sqrt(p/(n log^8 n)). The likely fix is p1 = sqrt(p/(n log^4 n)), which gives np1 = sqrt(np)/log^2 n and makes Lemma 3.5's condition hold, and also matches q = p1/log^2 n. But as written, the central Phase 1 construction has a concrete gap at exactly the point the reader flagged.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proves that for p ≥ log^{15} n / n, the binomial random digraph D_{n,p} contains, with high probability, exactly δ±(D_{n,p}) edge-disjoint directed Hamilton cycles, where δ± is the minimum of the minimum in-degree and the minimum out-degree. The proof has two phases: Phase 1 constructs a subdigraph D′ with δ± edge-disjoint 1-factors using a bipartite Gale–Ryser argument and a minimum-degree-gap theorem, and Phase 2 converts each 1-factor into a Hamilton cycle using an online sprinkling technique with double rotations. The paper claims this is optimal up to a polylogarithmic factor in p.","tokens_in":33795,"tokens_out":36970,"duration_ms":296381,"significance":"If the proof is correct, the result is a substantial advance: it establishes the exact bottleneck bound for edge-disjoint directed Hamilton cycles in random digraphs for all p down to polylogarithmic factors above the Hamiltonicity threshold. The proof contributes a useful staged generation of D_{n,p} and an online sprinkling method adapted to directed cycles. The structure is credible and the Phase 1 matching argument is elegant, but I find two load-bearing technical gaps that prevent me from endorsing the proof in its current form.","major_comments":[{"comment":"The weak tail bound for binomial variables is applied to Y1 ∼ Bin((np)^{1/3} log^2 n, log^7 n / √(np)). Its mean is (np)^{-1/6} log^9 n, which equals log^{6.5} n when p = log^{15} n / n. The stated weak-tail bound requires np < 1, so the displayed inequality Pr[X^1_e ≥ log^2 n] ≤ (np)^{1/3} log^2 n · (log^7 n/√(np))^{Ω(log^2 n)} is not justified. Moreover, a binomial with mean log^{6.5} n has Pr[Y1 ≥ log^2 n] close to 1, so this stochastic domination cannot yield the claimed o(1/n^2) unless one first proves a far stronger bound on the maximum of Des_F than Lemma 5.1 provides. A sharper control, e.g. max_u Des_F(u) = O(log n), would give X^1_e = O(√log n) for p = log^{15} n / n and make the argument work, but that step is missing. Since Lemma 5.5 is essential for coupling Phase 2 with D_{n,p1}, this is a load-bearing gap.","section":"Section 5.3, proof of Lemma 5.5, first term of (5.9)"},{"comment":"The statement that the case p = Θ(1) follows from methods in [26] is not supported by the cited result as presented in the paper, which is for d-regular digraphs with d ≥ (1/2+o(1))n. For p between the paper's ε = 88/(2(9e)^9) ≈ 10^{-8} and 1/2, D_{n,p} is not regular and typically has δ± < n/2, so the cited theorem does not apply. The proof in the paper only covers p ≤ ε. The theorem is stated for all p ≥ log^{15} n / n, so an additional argument is needed, for example splitting D_{n,p} into edge-disjoint copies of D_{n,ε} when p is a constant. As written, the proof of the full range is incomplete.","section":"Introduction and Section 2.1, reduction to p ≤ ε"},{"comment":"The displayed formulas for p1 and q are garbled: the text gives 'p1 = q p n log4 n' and 'q = q p n log8 n', which are not valid mathematical expressions. The only reading consistent with the chain in the proof of Lemma 3.5 and with the relation q = p1 / log^2 n in Section 5.3 is p1 = √(p/(n log^4 n)) and q = √(p/(n log^8 n)). If the literal alternative p1 = √(p log^4 n / n) were intended, then np1 = √(np) log^2 n, which is not o(√(np)/log n), so the degree-gap argument in Lemma 3.5 would fail. The authors should correct the typesetting and explicitly state the intended expressions.","section":"Procedure 1 and Section 5.3, definitions of p1 and q"}],"minor_comments":[{"comment":"In the description of right-rotation, 'or left-rotation for short' should read 'or right-rotation for short'.","section":"Section 4.1"},{"comment":"The sentence 'then (5.2) follows immediately by (5.1)' should refer to (5.3), not (5.2).","section":"Proof of Lemma 5.4, paragraph for (5.3)"},{"comment":"There is a typo: 'pitot vertex' should be 'pivot vertex'.","section":"Claim 5.6"},{"comment":"The statement should specify that the O(n^{-k}) bound is uniform over the choice of the k distinct matchings and over v ∈ [n]; the current wording is slightly ambiguous.","section":"Lemma B.1"},{"comment":"The sentence 'with high probability, the last part does not affect the minimum degree' would benefit from a one-line justification, since the random permutation π preserves in- and out-degrees exactly.","section":"Lemma 3.5, proof"}],"recommendation":"major_revision","confidential_remarks":"The core approach is promising and the paper contains several elegant ideas, but the proof of Lemma 5.5 has a genuine technical gap that affects the central coupling claim. In addition, the reduction from the full range of p to the range p ≤ ε is not justified as written. I believe both issues are repairable: Lemma 5.5 needs a sharper concentration analysis of Des_F, and the dense range can be handled by a standard edge-splitting argument. The provided text also has severe formula-rendering problems for p1 and q that should be fixed before resubmission."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper almost certainly proves the right theorem, but the written proof has a parameter inconsistency in Phase 1 that breaks Lemma 3.5. The headline result—ψ(D_{n,p}) = δ±(D_{n,p}) for all p ≥ log^15 n/n—is exactly the kind of closure the field wanted, and the high-level strategy is sensible: stage the generation of D_{n,p} to keep a subgraph with the right minimum degree, find δ edge-disjoint 1-factors via Gale-Ryser, then convert them to Hamilton cycles with online sprinkling. That's a credible plan, and the appendices do real work.\n\nThe soft spot is the definition of p1. Procedure 1 sets p1 = sqrt(p log^4 n / n) (or something equivalent), so np1 = sqrt(np) log^2 n. Lemma 3.5 requires sqrt(np0)/log n = ω(np1), but the ratio is 1/log^3 n. The chain in the proof is false: the last equality would need np1 = o(sqrt(np)/log^2 n). This kills the \"unique minimum-degree vertex survives the second exposure\" claim. Without that gap, the parameter γ = δ2(B) − δ(B) in Claim 3.7 can be zero, and the union bounds fall apart. Section 5.3 confirms the inconsistency: q = p1/log^2 n doesn't equal q = sqrt(p/(n log^8 n)) unless p1 is changed to sqrt(p/(n log^4 n)). That's a one-line fix, and I suspect it's the intended definition, but as written the Phase 1 argument is unsupported.\n\nThe reader flagged the degree gap as the weakest assumption; they were right, and the stress-test shows the failure is concrete. Still, this is not a conceptual collapse. The method is sound, the error is of the type that a careful referee would catch and the authors would fix. I'd send it to peer review, but with a clear request to correct p1 and re-check the concentration estimates. I would not cite it in current form.\n\nFor a reading group: maybe, as a case study in how parameter choices can break a long proof. It's a serious paper and deserves a serious referee, but the version on arXiv should not be the final one.","headline":"Right theorem, plausible strategy, but the printed p1 breaks Lemma 3.5 and needs a one-line parameter fix before this is citable.","tokens_in":34435,"tokens_out":6521,"would_cite":false,"duration_ms":49565,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C80","05C45","05C20"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves that for $p \\ge \\log^{15} n/n$, a typical random digraph $D_{n,p}$ contains exactly $\\delta^{\\pm}(D_{n,p})$ edge-disjoint directed Hamilton cycles, matching the trivial degree bottleneck upper bound.","keywords":["random directed graphs","edge-disjoint Hamilton cycles","minimum degree packing","1-factor decomposition","online sprinkling","rotation-extension technique","binomial random digraph","perfect matchings"],"falsifier":"Fix $p = C \\log^{15} n / n$ for a constant $C$ and, for large $n$, simulate Procedure 1 many times: draw the first bipartite graph with probability $p_0 \\approx p$, record its minimum-degree vertex $x^+$, add every edge incident to $x^+$ (and to the minimum-degree vertex $y^-$ of the other part) with probability $p_1 = \\sqrt{p/n}\\,\\log^4 n$, and check whether any other vertex's degree drops below $\\deg(x^+)$ after this second exposure. If this happens with non-negligible frequency, the equality $\\psi(D_{n,p}) = \\delta^{\\pm}(D_{n,p})$ cannot be established by this construction at that $p$. One can also simulate Phase 2 and count how many times a fixed edge is exposed; if that count ever reaches $\\Omega(\\log^2 n)$, the coupling back to $D_{n,p}$ breaks.","tokens_in":33196,"feed_emoji":"🔄","tokens_out":15419,"duration_ms":112015,"temperature":0.7,"pith_summary":"The paper proves that a typical binomial random digraph $D_{n,p}$ on $n$ vertices with edge probability $p \\ge \\log^{15} n / n$ contains exactly $\\delta^{\\pm}(D_{n,p})$ edge-disjoint directed Hamilton cycles, where $\\delta^{\\pm}$ is the smaller of the minimum out-degree and the minimum in-degree. Since every directed Hamilton cycle uses one incoming and one outgoing edge at each vertex, $\\delta^{\\pm}$ is an immediate upper bound; the theorem says that for almost every such digraph no other obstruction appears. The proof is a randomized algorithm that first extracts $\\delta^{\\pm}$ edge-disjoint 1-factors, collections of vertex-disjoint directed cycles covering all vertices, from a carefully generated subdigraph, and then splices each 1-factor into a single Hamilton cycle using fresh random edges exposed only when needed. This settles the packing problem for all $p$ above a polylogarithmic factor of the Hamiltonicity threshold.","feed_headline":"Random digraphs pack Hamilton cycles down to bottleneck degree","feed_subtitle":"A random digraph splits into as many edge-disjoint Hamilton cycles as its smallest in-/out-degree allows.","key_machinery":"The load-bearing structure is a bijection between balanced bipartite graphs and directed graphs fixed by a permutation $\\pi$: a bipartite edge $x_i y_j$ becomes the directed edge $i \\to \\pi(j)$. Procedure 1 exploits this by generating a bipartite graph $B$ in two exposures, isolating the two minimum-degree vertices, and then using a classical bipartite $r$-factor criterion (Theorem 3.2) to certify $\\delta$ edge-disjoint perfect matchings in $B$; the certification reduces to a single counting inequality whose proof rests on a high-probability gap between the minimum and second-minimum degrees in the first exposure. A uniformly random $\\pi$ then turns the matchings into $\\delta$ edge-disjoint 1-factors, each with $O(\\log n)$ cycles, because the identity $E[2^{\\sigma(\\pi)}] = n+1$ controls the cycle count of a random permutation. Phase 2's engine is the 'online sprinkling' double-rotation process: for each 1-factor, edges are exposed from a currently available set only when a rotation needs them, and the endpoint sets of rotated paths are shown to grow to size $\\Omega(\\log n / \\sqrt{q})$ in at most $\\log n / (4\\log\\log n)$ rounds; a newly exposed edge then closes the rotated path into a cycle. A third-moment bound on how often a vertex is chosen as a designated splicing vertex, together with a bound on how often any fixed edge is exposed, allows the freshly exposed edges to be coupled as a subgraph of the original $D_{n,p}$.","core_discovery":"The central discovery is that the trivial degree bottleneck is the whole story for typical random digraphs: with high probability $\\psi(D_{n,p}) = \\delta^{\\pm}(D_{n,p})$ whenever $p \\ge \\log^{15} n / n$. The argument achieves this by controlling the random digraph through a two-stage exposure: first a sparse bipartite encoding is generated and its minimum-degree vertices are identified, then all edges incident to those two vertices are re-exposed at a higher rate, so that the number of edge-disjoint perfect matchings forced by the bipartite encoding equals the minimum degree of the final digraph. These matchings become $\\delta^{\\pm}$ edge-disjoint 1-factors in a subdigraph $D' \\subseteq D_{n,p}$, each 1-factor having at most $4\\log n$ cycles. The remaining edges of $D_{n,p}$ are then exposed online, one 1-factor at a time, and a directed rotation-extension procedure splices the cycles of each 1-factor into a Hamilton cycle, with the total exposure of any single edge kept small enough to couple the whole process back to the original binomial distribution.","pith_inferences":["Editorial extension: the two-phase design — pack 1-factors first, then splice them — suggests a template for other packing problems in random structures where the bottleneck obstruction is purely local and the real difficulty is controlling the exposure of fresh randomness.","The polylog gap between $\\log^{15} n/n$ and the Hamiltonicity threshold $\\sim \\log n/n$ is probably an artifact of the rotation and sprinkling budget rather than a genuine obstruction, and a finer exposure analysis might push the equality toward the threshold.","A direct numerical check of the Phase 2 exposure counts for $p$ slightly below $\\log^{15} n/n$ would test whether the coupling lemma remains viable there; if the maximum number of exposures per edge stays $o(\\log^2 n)$, the same strategy could plausibly extend to smaller $p$.","The third-moment device used to bound designated-vertex usage may transfer to random hypergraph packing problems, where second-moment estimates are frequently too weak."],"forward_implications":["For every $p \\ge \\log^{15} n/n$, a typical $D_{n,p}$ achieves the trivial upper bound: its maximum number of edge-disjoint directed Hamilton cycles is exactly the bottleneck degree $\\delta^{\\pm}$.","The proof supplies a randomized polynomial-time algorithm that, with high probability, outputs $\\delta^{\\pm}$ pairwise edge-disjoint directed Hamilton cycles.","Since each Hamilton cycle uses every vertex once in and once out, the decomposition saturates every edge incident to a minimum-degree vertex, leaving no wasted capacity.","Combined with the known treatment of the constant-density regime, the equality now holds throughout the sparse regime above a polylog factor of the Hamiltonicity threshold.","The intermediate 1-factor decomposition gives a method to pack $\\delta$ edge-disjoint perfect matchings into a random bipartite graph whose minimum part-degree is $\\delta$."],"supporting_citations":[{"why":"Supplies the high-probability gap between the minimum and second-minimum degree of a random bipartite graph, which keeps the two exposed vertices minimal after the second exposure.","marker":"[4]"},{"why":"Introduces the online sprinkling idea used in Phase 2 to expose fresh edges only when needed and later couple them back to $D_{n,p}$.","marker":"[10]"},{"why":"Introduces the multiple-exposure generation of the random digraph that Procedure 1 adapts to control the minimum-degree vertices.","marker":"[11]"},{"why":"Gives the identity $E[2^{\\sigma(\\pi)}] = n+1$ used to show that each 1-factor contains at most $4\\log n$ cycles.","marker":"[12]"},{"why":"Provides the double-rotation technique for directed Hamilton cycles that the Phase 2 rotations generalize.","marker":"[13]"},{"why":"Supplies the two-sided minimum-degree bounds for the random bipartite graph used to calibrate $\\delta$ and verify the counting inequality.","marker":"[24]"},{"why":"Covers the dense regime where $p$ is a constant, so the new proof only needs to handle $p \\le \\varepsilon$.","marker":"[26]"},{"why":"Provides the bipartite $r$-factor criterion used to certify $\\delta$ edge-disjoint perfect matchings in $B$.","marker":"[29]"}],"fun_headline_variants":["Degree bottleneck is exact for random digraph Hamilton cycles","Random digraphs hit minimum-degree cap for edge-disjoint cycles","Typical random digraphs exactly hit the degree bottleneck","Minimum in/out degree fully determines Hamilton cycle packing","Random digraphs achieve optimal edge-disjoint Hamilton cycles"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The construction assumes that after the second exposure of edges incident to the two minimum-degree vertices of the first bipartite exposure, those vertices remain the unique minimum-degree vertices, so that the number of edge-disjoint perfect matchings found equals the minimum degree of the final random digraph $D_{n,p}$.","fun_headline_variants_meta":{"raw":{"variants":["Degree bottleneck is exact for random digraph Hamilton cycles","Random digraphs hit minimum-degree cap for edge-disjoint cycles","Typical random digraphs exactly hit the degree bottleneck","Minimum in/out degree fully determines Hamilton cycle packing","Random digraphs achieve optimal edge-disjoint Hamilton cycles"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00053,"raw_usage":{"total_tokens":2528,"prompt_tokens":896,"completion_tokens":1632,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":512,"completion_tokens_details":{"reasoning_tokens":1551}},"tokens_in":512,"tokens_out":1632,"duration_ms":10897,"temperature":1.0,"reasoning_tokens":1551,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-09T14:49:09.510570+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Fix $p = C \\log^{15} n / n$ for a constant $C$ and, for large $n$, simulate Procedure 1 many times: draw the first bipartite graph with probability $p_0 \\approx p$, record its minimum-degree vertex $x^+$, add every edge incident to $x^+$ (and to the minimum-degree vertex $y^-$ of the other part) with probability $p_1 = \\sqrt{p/n}\\,\\log^4 n$, and check whether any other vertex's degree drops below $\\deg(x^+)$ after this second exposure. If this happens with non-negligible frequency, the equality $\\psi(D_{n,p}) = \\delta^{\\pm}(D_{n,p})$ cannot be established by this construction at that $p$. One can also simulate Phase 2 and count how many times a fixed edge is exposed; if that count ever reaches $\\Omega(\\log^2 n)$, the coupling back to $D_{n,p}$ breaks.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the high-probability gap between the minimum and second-minimum degree of a random bipartite graph, which keeps the two exposed vertices minimal after the second exposure."},{"cited_title":"Ferber and V","cited_arxiv_id":null,"evidence_quote":"Introduces the online sprinkling idea used in Phase 2 to expose fresh edges only when needed and later couple them back to $D_{n,p}$."},{"cited_title":"4, 592–603","cited_arxiv_id":null,"evidence_quote":"Introduces the multiple-exposure generation of the random digraph that Procedure 1 adapts to control the minimum-degree vertices."},{"cited_title":"Cycle type of random permutations: A toolkit","cited_arxiv_id":"2104.12019","evidence_quote":"Gives the identity $E[2^{\\sigma(\\pi)}] = n+1$ used to show that each 1-factor contains at most $4\\log n$ cycles."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the double-rotation technique for directed Hamilton cycles that the Phase 2 rotations generalize."},{"cited_title":"Krivelevich and W","cited_arxiv_id":null,"evidence_quote":"Supplies the two-sided minimum-degree bounds for the random bipartite graph used to calibrate $\\delta$ and verify the counting inequality."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Covers the dense regime where $p$ is a constant, so the new proof only needs to handle $p \\le \\varepsilon$."},{"cited_title":"Lovász,Combinatorial problems and exercises, Vol","cited_arxiv_id":null,"evidence_quote":"Provides the bipartite $r$-factor criterion used to certify $\\delta$ edge-disjoint perfect matchings in $B$."}],"review_version":1}