Projects per year
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 language | English |
---|---|
Pages (from-to) | 157-178 |
Number of pages | 22 |
Journal | Combinatorics, Probability and Computing |
Volume | 33 |
Issue number | 2 |
Early online date | 8 Nov 2023 |
DOIs | |
Publication status | Published - Mar 2024 |
Bibliographical note
AcknowledgementsMuch of the research in this paper was carried out during a visit by the fourth and fifth authors to the University of Illinois at Urbana-Champaign. The authors are grateful to the BRIDGE strategic alliance between the University of Birmingham and the University of Illinois at Urbana-Champaign, which partially funded this visit. We thank Andrzej Dudek for pointing us towards Lemma 3.4, and to the referee for their careful review.
Keywords
- directed graphs
- cycles
- absorbing method
Fingerprint
Dive into the research topics of 'On oriented cycles in randomly perturbed digraphs'. Together they form a unique fingerprint.Projects
- 1 Finished
-
Matchings and tilings in graphs
Engineering & Physical Science Research Council
1/03/21 → 29/02/24
Project: Research Councils