Cycles of every length and orientation in randomly perturbed digraphs

Igor Araujo; Jozsef Balogh; Robert A. Krueger; Simon Piga; Andrew Treglown

doi:10.5817/CZ.MUNI.EUROCOMB23-009

Cycles of every length and orientation in randomly perturbed digraphs

Igor Araujo, Jozsef Balogh, Robert A. Krueger, Simon Piga, Andrew Treglown

Mathematics

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

11 Downloads (Pure)

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 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 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.

Original language	English
Title of host publication	EUROCOMB’23
Publisher	Masaryk University Press
Pages	1-8
Number of pages	8
DOIs	https://doi.org/10.5817/CZ.MUNI.EUROCOMB23-009
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)	2788-3116

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	https://iuuk.mff.cuni.cz/events/conferences/eurocomb23/

Access to Document

10.5817/CZ.MUNI.EUROCOMB23-009Licence: Creative Commons: Attribution-NonCommercial-NoDerivs (CC BY-NC-ND)

AraujoI2023CyclesFinal published version, 378 KBLicence: Creative Commons: Attribution-NonCommercial-NoDerivs (CC BY-NC-ND)

Matchings and tilings in graphs
Lo, A. & Treglown, A.
Engineering & Physical Science Research Council
1/03/21 → 29/02/24
Project: Research Councils

Cite this

@inproceedings{0e8c0c1bf8f5435a8bd480f1417b9f17,

title = "Cycles of every length and orientation in randomly perturbed digraphs",

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. ",

author = "Igor Araujo and Jozsef Balogh and Krueger, {Robert A.} and Simon Piga and Andrew Treglown",

year = "2023",

month = aug,

day = "28",

doi = "10.5817/CZ.MUNI.EUROCOMB23-009",

language = "English",

series = "European Conference on Combinatorics, Graph Theory and Applications",

publisher = "Masaryk University Press",

number = "12",

pages = "1--8",

booktitle = "EUROCOMB{\textquoteright}23",

note = "European Conference on Combinatorics, Graph Theory and Applications, EUROCOMB'23 ; Conference date: 28-08-2023 Through 01-09-2023",

url = "https://iuuk.mff.cuni.cz/events/conferences/eurocomb23/",

}

Araujo, I, Balogh, J, Krueger, RA, Piga, S & Treglown, A 2023, Cycles of every length and orientation in randomly perturbed digraphs. in EUROCOMB’23., 9, European Conference on Combinatorics, Graph Theory and Applications, no. 12, Masaryk University Press, pp. 1-8, European Conference on Combinatorics, Graph Theory and Applications, Prague, Czech Republic, 28/08/23. https://doi.org/10.5817/CZ.MUNI.EUROCOMB23-009

TY - GEN

T1 - Cycles of every length and orientation in randomly perturbed digraphs

AU - Araujo, Igor

AU - Balogh, Jozsef

AU - Krueger, Robert A.

AU - Piga, Simon

AU - Treglown, Andrew

PY - 2023/8/28

Y1 - 2023/8/28

N2 - 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.

AB - 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.

UR - https://journals.muni.cz/eurocomb

U2 - 10.5817/CZ.MUNI.EUROCOMB23-009

DO - 10.5817/CZ.MUNI.EUROCOMB23-009

M3 - Conference contribution

T3 - European Conference on Combinatorics, Graph Theory and Applications

SP - 1

EP - 8

BT - EUROCOMB’23

PB - Masaryk University Press

T2 - European Conference on Combinatorics, Graph Theory and Applications

Y2 - 28 August 2023 through 1 September 2023

ER -

Cycles of every length and orientation in randomly perturbed digraphs

Abstract

Publication series

Conference

Access to Document

Fingerprint

Projects

Matchings and tilings in graphs

Cite this