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 C_{n} 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.
Original language  English 

Title of host publication  EUROCOMB’23 
Publisher  Masaryk University Press 
Pages  18 
Number of pages  8 
DOIs  
Publication status  Published  28 Aug 2023 
Event  European Conference on Combinatorics, Graph Theory and Applications  Charles University, Faculty of Mathematics and Physics, Prague, Czech Republic Duration: 28 Aug 2023 → 1 Sept 2023 https://iuuk.mff.cuni.cz/events/conferences/eurocomb23/ 
Publication series
Name  European Conference on Combinatorics, Graph Theory and Applications 

Publisher  Masaryk University Press 
Number  12 
ISSN (Electronic)  27883116 
Conference
Conference  European Conference on Combinatorics, Graph Theory and Applications 

Abbreviated title  EUROCOMB'23 
Country/Territory  Czech Republic 
City  Prague 
Period  28/08/23 → 1/09/23 
Internet address 
Fingerprint
Dive into the research topics of 'Cycles of every length and orientation 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