On oriented cycles in randomly perturbed digraphs (Q6632800)

In this paper, the authors show that, for every \(\alpha >0\), there exists a constant \(C\) such that for every \(n\)-vertex digraph of minimum semi-degree at least \(\alpha n\), if one adds \(Cn\) random edges then asymptotically almost surely the resulting digraph contains every orientation of a cycle of every possible length, simultaneously. This result generalize a result due to \textit{T. Bohman} et al. [Random Struct. Algorithms 22, No. 1, 33--42 (2003; Zbl 1013.05044)]. Moreover, they prove that it is possible to relax the minimum semi-degree condition to a minimum total degree condition when considering orientations of a cycle that do not contain a large number of vertices of indegree \(1\).