Pith. sign in

REVIEW 2 minor 39 references

Universality for rainbow oriented cycles in perturbed digraphs

T0 review · 0 major / 2 minor · reviewed 2026-06-28 · grok-4.3

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

Pith's one-line read Randomly perturbed digraphs contain rainbow copies of every oriented cycle of every length with high probability.

desk verdict This unifies the uncolored perturbed-digraph result and the rainbow directed Hamilton result into one statement that covers every orientation and every cycle length at once. read the letter →

arxiv 2605.31398 v1 pith:MOYMCSBP submitted 2026-05-29 math.CO

Robert A. Krueger , David Staudinger This is my paper · ORCID
classification math.CO
keywords rainboworientedcyclesperturbeddigraphsdistributiveabsorptionrandomedgecoloringcycleuniversalityMontgomerymethod
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

A randomly perturbed digraph begins as an n-vertex digraph whose in- and out-degrees are each at least a positive linear fraction of n, then receives an additional linear number of random directed edges. When every edge is then colored independently and uniformly from a palette of n colors, the resulting object contains, with high probability, a rainbow copy of every orientation of every cycle whose length lies between 3 and n. These rainbow copies appear simultaneously for all orientations and all lengths. The result unifies earlier statements about uncolored perturbed digraphs and about rainbow Hamilton cycles that are consistently oriented.

What carries the argument

Montgomery's distributive absorption method, which successively embeds small rainbow oriented paths and absorbs them into larger rainbow cycles while preserving the rainbow property across all orientations.

What would settle it

Exhibit a concrete n-vertex digraph whose minimum in- and out-degree is linear in n, add a linear number of random edges, color the edges uniformly with n colors, and show that some orientation of some cycle length k (for example k=4) has no rainbow copy; if this occurs with probability bounded away from zero, the claim fails.

Watch

Extended reading notes

Core claim

In an n-vertex digraph with all in- and out-degrees linear in n, after the addition of a linear number of random edges and a uniform random coloring of all edges with n colors, there is with high probability a rainbow copy of every orientation of every cycle of length from 3 to n.

Load-bearing premise

The base digraph must already have in-degrees and out-degrees linear in n before the random edges are added, because the absorption argument relies on this minimum density.

Editorial extensions

If this is right

  • Every orientation of every k-cycle for 3 ≤ k ≤ n appears simultaneously as a rainbow subgraph.
  • The linear number of random edges suffices once the base degrees are linear.
  • The same perturbed model yields both the uncolored universality result and the rainbow Hamilton-cycle result for consistent orientations as special cases.
  • The distributive absorption technique succeeds in maintaining the rainbow condition while handling all orientations at once.

Reading between the lines

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

  • The same absorption framework could be tested on rainbow directed paths or on rainbow copies of other oriented graphs such as tournaments of fixed size.
  • If the number of colors were reduced to cn for c<1, long cycles would necessarily repeat colors, so the rainbow property would fail for lengths larger than roughly 1/c.
  • An undirected version might follow by replacing each undirected edge with a pair of opposite arcs and applying the same perturbation and coloring.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

0 major / 2 minor

Summary. The manuscript proves that an n-vertex digraph with all in- and out-degrees linear in n, after the addition of a linear number of random edges and a uniform random edge-coloring with n colors, contains with high probability a rainbow copy of every orientation of every cycle of every length from 3 to n, simultaneously. The argument is presented as a common generalization of the uncolored perturbed-digraph result of Araujo-Balogh-Krueger-Piga-Treglown and the rainbow directed Hamilton-cycle result of Katsamaktsis-Letzter-Sgueglia, obtained via Montgomery's distributive absorption method.

Significance. If correct, the result supplies a strong simultaneous-universality statement that unifies two active lines of research on perturbed digraphs and rainbow subgraphs. The extension of absorption techniques to handle all orientations and all lengths under a single random coloring is technically non-trivial; the paper appears to manage the necessary color-availability counting and union-bound arguments within the known regime for absorption lemmas. The explicit credit to prior theorems and the parameter-free character of the final statement (once the linear constants are fixed) are positive features.

minor comments (2)
  1. [Abstract] Abstract: the parenthetical remark 'linear number (depending on the degree)' leaves the precise functional dependence on the minimum degree implicit; a single sentence clarifying the admissible range of constants would improve readability for readers familiar with the absorption literature.
  2. [Introduction] The introduction would benefit from a short paragraph explicitly stating the linear constants required by the absorption lemmas invoked from Montgomery and from the two cited papers, so that the reader can immediately compare the hypotheses.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive assessment of the manuscript and for recommending acceptance. The report correctly identifies the result as a common generalization of the perturbed-digraph theorem of Araujo-Balogh-Krueger-Piga-Treglown and the rainbow directed Hamilton-cycle theorem of Katsamaktsis-Letzter-Sgueglia, obtained via Montgomery's distributive absorption method.

Circularity Check

0 steps flagged · score 2.0 of 10

Minor self-citation in cited prior work; central claim independent

full rationale

The paper presents a probabilistic existence result as a common generalization of two external theorems (uncolored perturbed digraphs and rainbow directed Hamilton cycles) via Montgomery's distributive absorption. One cited work shares an author (Krueger), but this is a standard non-load-bearing citation; the hypotheses match known regimes for absorption lemmas without any internal fitting, self-definition, or reduction of predictions to inputs by construction. The derivation is self-contained against external benchmarks.

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

Only the abstract is available, so no concrete free parameters, axioms, or invented entities can be extracted from the manuscript.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Universality for rainbow oriented cycles in perturbed digraphs." pith.science (2026). https://pith.science/paper/MOYMCSBP

@misc{pith2026260531398,
  author       = {Pith},
  title        = {Pith review of: Universality for rainbow oriented cycles in perturbed digraphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/MOYMCSBP}},
  note         = {Machine review of arXiv:2605.31398}
}
abstract

A randomly perturbed digraph is an $n$-vertex directed graph with all out- and in-degrees linear in $n$, to which a linear number (depending on the degree) of random edges have been randomly added. We show that randomly perturbed digraphs whose edges have been colored uniformly with $n$ colors have a rainbow copy of every orientation of every possible length cycle, simultaneously, with high probability. This is a common generalization of work of Araujo, Balogh, Krueger, Piga, and Treglown in the uncolored setting and Katsamaktsis, Letzter, and Sgueglia for consistently oriented spanning cycles. Our proof uses Montgomery's distributive absorption method.

Figures

Figures reproduced from arXiv: 2605.31398 by the authors.

Figure 1
Figure 1. ({c1, c2}, ⋆)-absorber with ⋆ = (→, ←, ⋆3, ⋆4, ⋆5, ←,→) and c1-absorbing and c2- absorbing paths shown. We use the short-hand notation for this gadget given on the left side of the figure in later constructions. Finally, by Theorem 7, D is (α, ε)-edge-color pseudorandom for some ε ≪ α (see Theo￾rem 6) with high probability, since C is sufficiently large. Thus by Theorem 8, we can find a path w2u1u2w3 of length 3 bet… view at source ↗
Figure 2
Figure 2. ({v1, v2}, ⋆)-absorber with ⋆ ∈ {→,←}48, (⋆i−1, ⋆i , ⋆i+1, ⋆i+2) = (← , → , → , ←) for some 3 ≤ i ≤ 7, and v1-absorbing and v2-absorbing paths shown. We use the short-hand notation for this gadget given on the left side of the figure in later constructions. 20 [PITH_FULL_IMAGE:figures/full_fig_p020_2.png] view at source ↗
Figure 3
Figure 3. ({v1, v2}, ⋆)-absorber with ⋆ ∈ {→, ←}48 , ⋆1 =→, ⋆2 =→, (⋆2, . . . , ⋆8) alternating, and v1-absorbing and v2-absorbing paths shown. We use the short-hand notation for this gadget given on the left side of the figure in later constructions. 22 [PITH_FULL_IMAGE:figures/full_fig_p022_3.png] view at source ↗
Figures from the paper (4 more)
Figure 4
Figure 4. Figure 4: A ({{vi , ci , di}}40 i=1,(→,←))-absorber. The {vi , ci , di}-absorbing path is simply u1viu2. • ⋆ 2 i = (⋆2046+10(i−1), . . . , ⋆2052+10(i−1)) for i ∈ [39], • ⋆ 3 i = (⋆2436+10(i−1), . . . , ⋆2442+10(i−1)) for i ∈ [39], • ⋆ 4 i = (⋆51i−2, ⋆51i−1, ⋆51i) for i ∈ [40], •…
Figure 5
Figure 5. Figure 5: ({v1, . . . , v40}, ⋆)-absorber, with v2-absorbing path shown. We use the short-hand notation for this gadget given on the left side of the figure in later constructions. 25 [PITH_FULL_IMAGE:figures/full_fig_p025_5.png]
Figure 6
Figure 6. Figure 6: ({c1, . . . , c40}, ⋆)-absorber, with c2-absorbing path shown. We use the short-hand notation for this gadget given on the left side of the figure in later constructions. 27 [PITH_FULL_IMAGE:figures/full_fig_p027_6.png]
Figure 7
Figure 7. Figure 7: X µn -absorber, with a particular U-absorbing path shown. Local absorbers within global absorber are activated based on matching between Z ′ and U ′ ∪ Y ′ in the robustly matchable auxiliary graph H. 29 [PITH_FULL_IMAGE:figures/full_fig_p029_7.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

39 extracted references · 6 canonical work pages

  1. [1]

    Aigner-Horev and D

    E. Aigner-Horev and D. Hefetz. Rainbow Hamilton cycles in randomly colored randomly perturbed dense graphs.SIAM Journal on Discrete Mathematics, 35(3):1569–1577, 2021

    2021

  2. [2]

    Ajtai, J

    M. Ajtai, J. Koml´ os, and E. Szemer´ edi. First occurrence of Hamilton cycles in random graphs.North-Holland Mathematics Studies, 115(C):173–178, 1985

    1985

  3. [3]

    Anastos and A

    M. Anastos and A. Frieze. How many randomly colored edges make a randomly colored dense graph rainbow Hamiltonian or rainbow connected?Journal of Graph Theory, 92(4):405–414, 2019

    2019

  4. [4]

    L. D. Andersen. Hamilton circuits with many colours in properly edge-coloured complete graphs.Mathematica Scandinavica, pages 5–14, 1989

    1989

  5. [5]

    Araujo, J

    I. Araujo, J. Balogh, R. A. Krueger, S. Piga, and A. Treglown. On oriented cycles in randomly perturbed digraphs.Combinatorics, Probability and Computing, 33(2):157– 178, 2024

    2024

  6. [6]

    Bal and A

    D. Bal and A. Frieze. Rainbow matchings and Hamilton cycles in random graphs. Random Structures & Algorithms, 48(3):503–523, 2016

    2016

  7. [7]

    Balogh and T

    J. Balogh and T. Molla. Long rainbow cycles and Hamiltonian cycles using many colors in properly edge-colored complete graphs.European Journal of Combinatorics, 79:140– 151, 2019

    2019

  8. [8]

    Barber, S

    B. Barber, S. Glock, D. K¨ uhn, A. Lo, R. Montgomery, and D. Osthus. Minimalist designs.Random Structures & Algorithms, 57(1):47–63, 2020

    2020

Show all 39 references
  1. [9]

    Benzing, A

    F. Benzing, A. Pokrovskiy, and B. Sudakov. Long directed rainbow cycles and rainbow spanning trees.European Journal of Combinatorics, 88:103102, 2020. 33

    2020

  2. [10]

    Bohman, A

    T. Bohman, A. Frieze, and R. Martin. How many random edges make a dense graph Hamiltonian?Random Structures & Algorithms, 22(1):33–42, 2003

    2003

  3. [11]

    Bollob´ as

    B. Bollob´ as. The evolution of sparse graphs.Graph theory and combinatorics (Cam- bridge, 1983), pages 35–57, 1984

    1983

  4. [12]

    B´ ar´ any

    I. B´ ar´ any. A generalization of Carath´ eodory’s theorem.Discrete Mathematics, 40(2):141–152, 1982

    1982

  5. [13]

    Cooper and A

    C. Cooper and A. Frieze. Multi-coloured Hamilton cycles in random edge-coloured graphs.Combinatorics, Probability and Computing, 11(2):129–133, 2002

    2002

  6. [14]

    DeBiasio, D

    L. DeBiasio, D. K¨ uhn, T. Molla, D. Osthus, and A. Taylor. Arbitrary orientations of Hamilton cycles in digraphs.SIAM Journal on Discrete Mathematics, 29(3):1553–1584, 2015

    2015

  7. [15]

    DeBiasio and T

    L. DeBiasio and T. Molla. Semi-degree threshold for anti-directed Hamiltonian cycles. The Electronic Journal of Combinatorics, 22(4):P4.34, 2015

    2015

  8. [16]

    Delcourt and L

    M. Delcourt and L. Postle. Refined absorption: A new proof of the existence conjecture. arXiv preprint arXiv:2402.17855, 2024

    2024

  9. [17]

    A. E. D´ ıaz and R. V. Razafindravola. How many random edges make an almost-Dirac graph Hamiltonian?arXiv preprint arXiv:2410.14447, 2024

    2024

  10. [18]

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

    1952

  11. [19]

    A. Ferber. Closing gaps in problems related to Hamilton cycles in random graphs and hypergraphs.The Electronic Journal of Combinatorics, 22(1):P1.61, 2015

    2015

  12. [20]

    Ferber and M

    A. Ferber and M. Krivelevich. Rainbow Hamilton cycles in random graphs and hyper- graphs. InRecent trends in combinatorics, pages 167–189. Springer, 2016

    2016

  13. [21]

    Frieze and P.-S

    A. Frieze and P.-S. Loh. Rainbow Hamilton cycles in random graphs.Random Structures & Algorithms, 44(3):328–354, 2014

    2014

  14. [22]

    Ghouila-Houri

    A. Ghouila-Houri. Une condition suffisante dexistence dun circuit Hamiltonien.Comptes Rendus Hebdomadaires Des Seances De L Academie Des Sciences, 251(4):495–497, 1960

    1960

  15. [23]

    Glock, D

    S. Glock, D. K¨ uhn, A. Lo, and D. Osthus.The existence of designs via iterative absorp- tion: hypergraph F-designs for arbitrary F, volume 284, monograph 1046. American Mathematical Society, 2023

    2023

  16. [24]

    Gould, T

    S. Gould, T. Kelly, D. K¨ uhn, and D. Osthus. Almost all optimally coloured complete graphs contain a rainbow Hamilton path.Journal of Combinatorial Theory, Series B, 156:57–100, 2022. 34

    2022

  17. [25]

    Hahn-Klimroth, G

    M. Hahn-Klimroth, G. Maesaka, Y. Mogge, S. Mohr, and O. Parczyk. Random pertur- bation of sparse graphs.The Electronic Journal of Combinatorics, 28(2):P2.26, 2021

    2021

  18. [26]

    S. Janson. New versions of Suen’s correlation inequality.Random Structures and Algo- rithms, 13(3-4):467–483, 1998

    1998

  19. [27]

    Joos and J

    F. Joos and J. Kim. On a rainbow version of Dirac’s theorem.Bulletin of the London Mathematical Society, 52(3):498–504, 2020

    2020

  20. [28]

    R. M. Karp.Reducibility among Combinatorial Problems. Springer US, Boston, MA, pages 85–103, 1972

    1972

  21. [29]

    Katsamaktsis, S

    K. Katsamaktsis, S. Letzter, and A. Sgueglia. Rainbow Hamiltonicity in uniformly coloured perturbed digraphs.Combinatorics, Probability and Computing, 33(5):624– 642, 2024

    2024

  22. [30]

    P. Keevash. The existence of designs.arXiv preprint arXiv:1401.3665, 2014

    2014

  23. [31]

    Krivelevich

    M. Krivelevich. Long paths and Hamiltonicity in random graphs.arXiv preprint arXiv:1507.00205, 2015

    2015 arXiv

  24. [32]

    McDiarmid

    C. McDiarmid. General first-passage percolation.Advances in Applied Probability, 15(1):149–161, 1983

    1983

  25. [33]

    Montgomery

    R. Montgomery. Spanning trees in random graphs.Advances in Mathematics, 356:106793, 2019

    2019

  26. [34]

    Montgomery

    R. Montgomery. A proof of the Ryser–Brualdi–Stein conjecture for large evenn.arXiv preprint arXiv:2310.19779, 2023

    2023

  27. [35]

    Montgomery

    R. Montgomery. Spanning cycles in random directed graphs.Random Structures & Algorithms, 65(3):535–575, 2024

    2024

  28. [36]

    Pokrovskiy.Rainbow Subgraphs and their Applications

    A. Pokrovskiy.Rainbow Subgraphs and their Applications. London Mathematical Society Lecture Note Series. Cambridge University Press, pages 191–214, 2022

    2022

  29. [37]

    L. P´ osa. Hamiltonian circuits in random graphs.Discrete Mathematics, 14(4):359–364, 1976

    1976

  30. [38]

    R¨ odl, A

    V. R¨ odl, A. Ruci´ nski, and E. Szemer´ edi. A dirac-type theorem for 3-uniform hyper- graphs.Combinatorics, Probability and Computing, 15(1-2):229–251, 2006

    2006

  31. [39]

    W. Sun, G. Wang, and L. Wei. Transversal structures in graph systems: A survey. arXiv preprint arXiv:2412.01121, 2024. 35

    2024 arXiv

Pith tools

Reviewed June 28, 2026 · model on record in the stance chip above.