On oriented cycles in randomly perturbed digraphs

arXiv2212.10112MaRDI QIDQ6421080FDOQ6421080

Authors: Igor Araujo, József Balogh, Robert A. Krueger, Simón Piga, Andrew Treglown 

Publication date: 20 December 2022

Abstract: In 2003, Bohman, Frieze, and Martin initiated the study of randomly perturbed graphs and digraphs. For digraphs, they showed that for every $alpha>0$, there exists a constant $C$ such that for every $n$-vertex digraph of minimum semi-degree at least $alphan$, if one adds $Cn$ random edges then asymptotically almost surely the resulting digraph contains a consistently oriented Hamilton cycle. We generalize their result, showing that the hypothesis of this theorem actually asymptotically almost surely ensures the existence of every orientation of a cycle of every possible length, simultaneously. Moreover, we prove that we can 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$. Our proofs make use of a variant of an absorbing method of Montgomery.

This page was built for publication: On oriented cycles in randomly perturbed digraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6421080)