Overview
This study investigates the presence of rainbow oriented cycles in randomly perturbed digraphs. The research suggests that such digraphs contain, with high probability, a rainbow copy of every orientation of every possible length cycle simultaneously. This observation is made when the digraph's edges are uniformly colored with $n$ colors.
Research Context
The concept of a randomly perturbed digraph involves an $n$-vertex directed graph characterized by out- and in-degrees that are linear in $n$. To this base structure, a linear number of random edges are added, where the quantity of added edges is dependent on the degree. The edges of the digraph are then uniformly colored using $n$ distinct colors. This work builds upon and generalizes prior research, specifically work by Araujo, Balogh, Krueger, Piga, and Treglown in uncolored graph settings, and by Katsamaktsis, Letzter, and Sgueglia concerning consistently oriented spanning cycles.
Approach
The methodology employed for this proof leverages Montgomery's distributive absorption method. This approach allows for the analysis of the structure within randomly perturbed digraphs to ascertain the presence of the specified cycle types.
Findings
- Randomly perturbed digraphs, where all out- and in-degrees are linear in $n$, and to which a linear number of random edges proportional to the degree have been added, exhibit specific properties.
- When the edges of these digraphs are uniformly colored with $n$ colors, they simultaneously contain a rainbow copy of every orientation of every possible length cycle.
- This simultaneous presence of rainbow oriented cycles is observed with high probability.
- The research generalizes prior findings from uncolored graph contexts and those focused solely on consistently oriented spanning cycles.