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 nvertex digraph of minimum semidegree 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 semidegree 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 (fromto)  157178 
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 UrbanaChampaign. The authors are grateful to the BRIDGE strategic alliance between the University of Birmingham and the University of Illinois at UrbanaChampaign, 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