Pith. sign in

REVIEW 3 major objections 5 minor 43 references

Minimum degree edge-disjoint Hamilton cycles in random directed graphs

T0 review · 3 major / 5 minor · reviewed 2026-08-09 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read 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.

desk verdict Right theorem, plausible strategy, but the printed p1 breaks Lemma 3.5 and needs a one-line parameter fix before this is citable. read the letter →

arxiv 2502.01631 v1 pith:YN5QEPUQ submitted 2025-02-03 math.CO

Asaf Ferber , Adva Mond This is my paper · ORCID
classification math.CO MSC 05C8005C4505C20
keywords randomdirectedgraphsedge-disjointHamiltoncyclesminimumdegreepacking1-factordecompositiononlinesprinklingrotation-extensiontechniquebinomialdigraphperfectmatchings
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

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.

What carries the argument

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}$.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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}$.

Editorial extensions

If this is right

  • 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$.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 5 minor

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.

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 (3)
  1. [Section 5.3, proof of Lemma 5.5, first term of (5.9)] 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.
  2. [Introduction and Section 2.1, reduction to p ≤ ε] 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.
  3. [Procedure 1 and Section 5.3, definitions of p1 and q] 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.
minor comments (5)
  1. [Section 4.1] In the description of right-rotation, 'or left-rotation for short' should read 'or right-rotation for short'.
  2. [Proof of Lemma 5.4, paragraph for (5.3)] The sentence 'then (5.2) follows immediately by (5.1)' should refer to (5.3), not (5.2).
  3. [Claim 5.6] There is a typo: 'pitot vertex' should be 'pivot vertex'.
  4. [Lemma B.1] 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.
  5. [Lemma 3.5, proof] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the proof derives the bottleneck lower bound from external matching and concentration results rather than assuming it.

full rationale

The paper's central claim, Theorem 1.1, is not assumed in the proof. Phase 1 generates a subdigraph D' via a three-stage exposure and proves, using the external Gale-Ryser criterion and Bollobás's degree-gap theorem, that D' contains δ edge-disjoint 1-factors, where δ is the degree of the two minimum-degree vertices after the second exposure; Lemma 3.5 then establishes that this δ coincides with δ±(D_{n,p}) with high probability. This is a proved high-probability identification, not a definitional identity or a fitted parameter. Phase 2 converts the 1-factors into Hamilton cycles by an online sprinkling procedure whose exposure budget is controlled by Lemmas 5.1 and 5.5, both proved in the paper using Chernoff bounds and third-moment estimates. The citations to the authors' earlier works [10,11] supply techniques (online sprinkling and staged generation of random digraphs) but not the target theorem; no load-bearing step invokes a uniqueness theorem, no quantity is renamed from a fit into a prediction, and no known result is repackaged as a new derivation. All load-bearing estimates are derived in-paper from standard external inequalities, so no circular step is present.

Assumptions & free parameters 4 free parameters · 5 assumptions · 0 invented entities

The paper introduces no new primitive entities such as particles, forces, or dimensions. The only auxiliary quantities are algorithmic parameters (p0, p1, q, ε) that are chosen by hand to make the proof work. The mathematical background used is standard and explicitly cited.

free parameters (4)
  • p0 = satisfies (1-p0)(1-p1)=1-p
    Edge probability for the first exposure in Procedure 1; chosen by hand to split the generation of D_{n,p} into two phases.
  • p1 = sqrt(p/(n log^4 n))
    Edge probability for the second exposure and the reservoir for online sprinkling; chosen to balance the number of 1-factors and the availability of extra edges.
  • q = sqrt(p/(n log^8 n)) = p1/log^2 n
    Per-exposure probability in the online sprinkling phase; chosen so that no edge is exposed more than log^2 n times with high probability.
  • epsilon = 88/(2(9e)^9)
    Small constant upper bound on p used in Proposition 3.11 to guarantee the no-heavy-vertices property; chosen to make a union bound o(n^{-3}).
assumptions (5)
  • standard math Chernoff bound for binomial random variables (Theorem 3.1).
    Used throughout the paper for concentration of degrees and edge counts.
  • standard math Gale-Ryser theorem for the existence of an r-factor in a bipartite graph (Theorem 3.2).
    Gives the condition (3.1) used to find δ edge-disjoint perfect matchings in the bipartite graph B.
  • standard math Bollobás's theorem on the gap between the minimum and second-minimum degree of a random bipartite graph (Theorem 3.3).
    Provides the unique minimum-degree vertex and the degree gap needed for Lemma 3.5 and Lemma 3.6.
  • standard math König's theorem that regular bipartite graphs decompose into perfect matchings.
    Converts the δ-factor obtained from Gale-Ryser into δ edge-disjoint perfect matchings.
  • domain assumption The random digraph model D_{n,p} with independent directed edges and no loops.
    The object of study; the proof works entirely within this standard model.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Minimum degree edge-disjoint Hamilton cycles in random directed graphs." pith.science (2026). https://pith.science/paper/YN5QEPUQ

@misc{pith2026250201631,
  author       = {Pith},
  title        = {Pith review of: Minimum degree edge-disjoint Hamilton cycles in random directed graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/YN5QEPUQ}},
  note         = {Machine review of 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_{n,p}$. We show that a typical $D_{n,p}$ contains precisely the minimum between the minimum out- and in-degrees many edge-disjoint Hamilton cycles, given that $p\geq \log^{15} n/n$, which is optimal up to a factor of poly$\log n$. Our proof provides a randomized algorithm to generate the cycles and uses a novel idea of generating $D_{n,p}$ 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.

Figures

Figures reproduced from arXiv: 2502.01631 by the authors.

Figure 1
Figure 1. A path P, left- and right-rotations of it with pivots (x, y) and (w, z), respectively, and a path obtained by rotations from both sides. below, considering only vertices from V1, V2 and from V3, V4 for left- and right-rotations, respectively, makes our proof simpler. Online sprinkling left rotations. Given a path P = (u1, . . . , um) in a digraph D′ on n vertices and a subset of available edges E′ , do the following… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

43 extracted references · 42 canonical work pages

  1. [26]

    , Hamilton decompositions of regular expanders: a proof of kelly’s conjecture for large tournaments, Advances in Mathematics 237 (2013), 62–146

    work page 2013

  2. [1]

    Alon and J.H

    N. Alon and J.H. Spencer,The Probabilistic Method, John Wiley & Sons, 2004

    work page 2004

  3. [2]

    Ben-Shimon, M

    S. Ben-Shimon, M. Krivelevich, and B. Sudakov,On the resilience of hamiltonicity and optimal packing of hamilton cycles in random graphs, SIAM Journal on Discrete Mathematics25 (2011), no. 3, 1176–1193

    work page 2011

  4. [3]

    Bollobás,The evolution of sparse graphs, Graph theory and combinatorics (Cambridge, 1983) (1984), 35–57

    B. Bollobás,The evolution of sparse graphs, Graph theory and combinatorics (Cambridge, 1983) (1984), 35–57

    work page 1984

  5. [4]

    , Random graphs, Springer, 1998

    work page 1998

  6. [5]

    Bollobás and A

    B. Bollobás and A. M. Frieze,On matchings and hamiltonian cycles in random graphs., Carnegie-Mellon Univ. Pittsburgh PA Management Sciences Research Group, 1983

    work page 1983

  7. [6]

    Csaba, D

    B. Csaba, D. Kühn, A. Lo, D. Osthus, and A. Treglown,Proof of the 1-factorization and hamilton decomposition conjectures, Vol. 244, American Mathematical Society, 2016

    work page 2016

  8. [7]

    G. A. Dirac,Some theorems on abstract graphs, Proceedings of the London Mathematical Society3 (1952), no. 1, 69–81

    work page 1952

Show all 43 references
  1. [8]

    Ferber, M

    A. Ferber, M. Krivelevich, and B. Sudakov,Counting and packing hamilton cycles in dense graphs and oriented graphs, Journal of Combinatorial Theory, Series B122 (2017), 196–220

    2017

  2. [9]

    Ferber, G

    A. Ferber, G. Kronenberg, and E. Long,Packing, counting and covering hamilton cycles in random directed graphs, Israel Journal of Mathematics220 (2017), no. 1, 57–87

    2017

  3. [10]

    Ferber and V

    A. Ferber and V. Vu,Packing perfect matchings in random hypergraphs, Random Structures & Algorithms52 (2018), no. 3, 367–378

    2018

  4. [11]

    4, 592–603

    Asaf Ferber, Matthew Kwan, and Benny Sudakov,Counting hamilton cycles in sparse random directed graphs, Random Structures & Algorithms53 (2018), no. 4, 592–603

    2018

  5. [12]

    Ford,Cycle type of random permutations: A toolkit, arXiv preprint arXiv:2104.12019 (2021)

    K. Ford,Cycle type of random permutations: A toolkit, arXiv preprint arXiv:2104.12019 (2021)

    2021 arXiv

  6. [13]

    A. M. Frieze,An algorithm for finding hamilton cycles in random directed graphs, Journal of Algorithms9 (1988), no. 2, 181–204

    1988

  7. [14]

    A. M. Frieze and M. Krivelevich,On packing hamilton cycles inε-regular graphs, Journal of Combinatorial Theory, Series B 94 (2005), no. 1, 159–172

    2005

  8. [15]

    1, 221–234

    , On two hamilton cycle problems in random graphs, Israel Journal of Mathematics166 (2008), no. 1, 221–234

    2008

  9. [16]

    Ghouila-Houri,Une condition suffisante dexistence dun circuit hamiltonien, Comptes Rendus Hebdomadaires Des Seances De L’Academie Des Sciences251 (1960), no

    A. Ghouila-Houri,Une condition suffisante dexistence dun circuit hamiltonien, Comptes Rendus Hebdomadaires Des Seances De L’Academie Des Sciences251 (1960), no. 4, 495–497

    1960

  10. [17]

    Häggkvist,Hamilton cycles in oriented graphs, Combinatorics, Probability and Computing2 (1993), no

    R. Häggkvist,Hamilton cycles in oriented graphs, Combinatorics, Probability and Computing2 (1993), no. 1, 25–32

    1993

  11. [18]

    Janson, A

    S. Janson, A. Ruciński, and T. Łuczak,Random Graphs, John Wiley & Sons, 2000

    2000

  12. [19]

    R. M. Karp,Reducibility among combinatorial problems, Complexity of computer computations, 1972, pp. 85–103

    1972

  13. [20]

    Keevash, D

    P. Keevash, D. Kühn, and D. Osthus,An exact minimum degree condition for hamilton cycles in oriented graphs, Journal of the London Mathematical Society79 (2009), no. 1, 144–166

    2009

  14. [21]

    F. Knox, D. Kühn, and D. Osthus,Approximate hamilton decompositions of random graphs, Random Structures & Algorithms 40 (2012), no. 2, 133–149

    2012

  15. [22]

    3, 397–445

    , Edge-disjoint hamilton cycles in random graphs, Random Structures & Algorithms46 (2015), no. 3, 397–445

    2015

  16. [23]

    Komlós and E

    J. Komlós and E. Szemerédi,Limit distribution for the existence of hamiltonian cycles in a random graph, Discrete mathematics 43 (1983), no. 1, 55–63

    1983

  17. [24]

    Krivelevich and W

    M. Krivelevich and W. Samotij,Optimal packings of hamilton cycles in sparse random graphs, SIAM Journal on Discrete Mathematics 26 (2012), no. 3, 964–982

    2012

  18. [25]

    Kühn and D

    D. Kühn and D. Osthus,A survey on hamilton cycles in directed graphs, European Journal of Combinatorics33 (2012), no. 5, 750–766

    2012

  19. [27]

    , Hamilton cycles in graphs and hypergraphs: an extremal perspective, arXiv preprint arXiv:1402.4268 (2014)

    2014 arXiv

  20. [28]

    , Hamilton decompositions of regular expanders: applications, Journal of Combinatorial Theory, Series B 104 (2014), 1–27

    2014

  21. [29]

    Lovász,Combinatorial problems and exercises, Vol

    L. Lovász,Combinatorial problems and exercises, Vol. 361, American Mathematical Soc., 2007

    2007

  22. [30]

    McDiarmid,Clutter percolation and random graphs, Combinatorial optimization ii, 1980, pp

    C. McDiarmid,Clutter percolation and random graphs, Combinatorial optimization ii, 1980, pp. 17–25

    1980

  23. [31]

    C. S. J. Nash-Williams,Edge-disjoint hamiltonian circuits in graphs with vertices of large valency, Studies in pure mathematics (presented to richard rado), 1971, pp. 157–183

    1971

  24. [32]

    Pósa,Hamiltonian circuits in random graphs, Discrete Mathematics14 (1976), no

    L. Pósa,Hamiltonian circuits in random graphs, Discrete Mathematics14 (1976), no. 4, 359–364. 21 A Proof of Lemma 4.2 We start with reminding the lemma proved in this appendix and the relevant notation. LetD′ = (V, E) be a digraph onn vertices, let P = (u1, . . . , um) be a pa...

    1976

  25. [33]

    eG T, π−1(T ) ⩾ c1 + c2 + c3, and

  26. [34]

    the subgraph ofG induced by (T ∪ {v}) ∪ π−1(T ∪ {v}) has no isolated vertices, and

  27. [35]

    These observations are sufficient to prove the following claim: Claim B.2

    π−1(v) ∈ Y has three neighbors inT ∪ {v}. These observations are sufficient to prove the following claim: Claim B.2. P(|T | = O(1)) = O(n−3). Proof. Conditioning on the size ofT, we distinguish between two cases: Case 1. vπ −1(v) /∈ E(G). In this case, there aren − 3 possible ...

  28. [36]

    Initialize by settingU = ∅ (the set of labeled vertices)

  29. [37]

    (ii) While P is not a directed cycle, do the following step: Note that the componentP is either a directed path or an isolated vertex

    For 1 ⩽ i ⩽ 3, do the following: (i) Let P be the directed component containing the vertexv in D[Mi, U]. (ii) While P is not a directed cycle, do the following step: Note that the componentP is either a directed path or an isolated vertex. Letx be the sink ofP and let y ∈ Y be...

  30. [38]

    This procedure incrementally reveals the permutationπ by following the edges of the matchings M1, M2, and M3 that define the cyclesC1, C2, and C3, repectively, inDπ

    Expose the remaining labels in[n] \ U in arbitrary order. This procedure incrementally reveals the permutationπ by following the edges of the matchings M1, M2, and M3 that define the cyclesC1, C2, and C3, repectively, inDπ. The key idea is to start at the vertex v, trace its u...

  31. [39]

    the path is of lengthcs − 1, and

  32. [40]

    Note that ifz is the other endpoint of the path, and we considerz ∈ X, then in order to close the cycle, its unique neighbor inMs, if yet unlabeled, must be labeledw

    there is exactly one vertexw (the starting point of this path) that remains unlabeled at this stage; that is,π−1(w) is yet undefined. Note that ifz is the other endpoint of the path, and we considerz ∈ X, then in order to close the cycle, its unique neighbor inMs, if yet unlab...

  33. [41]

    For everyi ∈ [δ], E 1 c3 i = O 1 n

  34. [42]

    For every distincti, j∈ [δ], E 1 c2 i cj = O log2 n n2

  35. [43]

    For every distincti, j, k∈ [δ], E 1 cicj ck = O log3 n n3 . Proof. We start by showing statement (1). Note that for a single cycle, the probabilityP(ci = t) = 1/n. Hence, E 1 c3 i ! = X ai∈[n] 1 a3 i P(ci = ai) = 1 n X ai∈[n] 1 a3 i = O 1 n . To prove statement (2) and (3) we ...

Pith tools

Reviewed August 9, 2026 · model on record in the stance chip above.