On oriented cycles in randomly perturbed digraphs

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

Research output: Contribution to journalArticlepeer-review

Abstract

In 2003, Bohman, Frieze, and Martin initiated the study of randomly perturbed graphs and digraphs. For digraphs, they showed that for every α > 0, there exists a constant C such that for every n-vertex digraph of minimum semi-degree at least án, 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.

Original languageEnglish (US)
JournalCombinatorics Probability and Computing
DOIs
StateAccepted/In press - 2023

Keywords

  • absorbing method
  • cycles
  • directed graphs

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Statistics and Probability
  • Computational Theory and Mathematics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'On oriented cycles in randomly perturbed digraphs'. Together they form a unique fingerprint.

Cite this