pith. sign in

arxiv: 2605.31398 · v1 · pith:MOYMCSBPnew · submitted 2026-05-29 · 🧮 math.CO

Universality for rainbow oriented cycles in perturbed digraphs

Robert A. Krueger , David Staudinger This is my paper

Pith reviewed 2026-06-28 22:02 UTC · model grok-4.3

classification 🧮 math.CO
keywords rainbow oriented cyclesperturbed digraphsdistributive absorptionrandom edge coloringcycle universalitydigraphsMontgomery method
0
0 comments X

The pith

Randomly perturbed digraphs contain rainbow copies of every oriented cycle of every length with high probability.

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

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.

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.

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.

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.

Where Pith is reading between the lines

These are 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.

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.

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.

Figures

Figures reproduced from arXiv: 2605.31398 by David Staudinger, Robert A. Krueger.

Figure 1
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 le… view at source ↗
Figure 2
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. 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 ↗
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], • ⋆ 5 i = (⋆10i+2033, ⋆10i+2034, ⋆10i+2035) for i ∈ [39], • ⋆ 6 i = (⋆10i+2434, ⋆10i+2435, ⋆10i+2436) for i ∈ [39]. First we apply Theorem 16… view at source ↗
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] view at source ↗
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] view at source ↗
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] view at source ↗
read the original 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.

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 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

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.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

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

pith-pipeline@v0.9.1-grok · 5639 in / 972 out tokens · 35890 ms · 2026-06-28T22:02:42.917617+00:00 · methodology

discussion (0)

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

Reference graph

Works this paper leans on

39 extracted references · 6 canonical work pages · 2 internal anchors

  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

  9. [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

  10. [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

  11. [11]

    Bollob´ as

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

    1983

  12. [12]

    B´ ar´ any

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

    1982

  13. [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

  14. [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

  15. [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

  16. [16]

    Refined Absorption: A New Proof of the Existence Conjecture

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

    work page arXiv 2024

  17. [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

    work page arXiv 2024

  18. [18]

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

    1952

  19. [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

  20. [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

  21. [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

  22. [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

  23. [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

  24. [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

  25. [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

  26. [26]

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

    1998

  27. [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

  28. [28]

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

    1972

  29. [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

  30. [30]

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

    work page arXiv 2014

  31. [31]

    Long paths and Hamiltonicity in random graphs

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

    work page internal anchor Pith review Pith/arXiv arXiv 2015

  32. [32]

    McDiarmid

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

    1983

  33. [33]

    Montgomery

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

    2019

  34. [34]

    Montgomery

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

    work page arXiv 2023

  35. [35]

    Montgomery

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

    2024

  36. [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

  37. [37]

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

    1976

  38. [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

  39. [39]

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

    work page internal anchor Pith review Pith/arXiv arXiv 2024