TY - JOUR

T1 - Robust Hamiltonicity of random directed graphs

AU - Ferber, Asaf

AU - Nenadov, Rajko

AU - Noever, Andreas

AU - Peter, Ueli

AU - Škorić, Nemanja

PY - 2017

Y1 - 2017

N2 - In his seminal paper from 1952 Dirac showed that the complete graph on n≥3 vertices remains Hamiltonian even if we allow an adversary to remove ⌊n/2⌋ edges touching each vertex. In 1960 Ghouila-Houri obtained an analogue statement for digraphs by showing that every directed graph on n≥3 vertices with minimum in- and out-degree at least n/2 contains a directed Hamilton cycle. Both statements quantify the robustness of complete graphs (digraphs) with respect to the property of containing a Hamilton cycle.A natural way to generalize such results to arbitrary graphs (digraphs) is using the notion of local resilience. The local resilience of a graph (digraph) G with respect to a property P is the maximum number r such that G has the property P even if we allow an adversary to remove an r-fraction of (in- and out-going) edges touching each vertex. The theorems of Dirac and Ghouila-Houri state that the local resilience of the complete graph and digraph with respect to Hamiltonicity is 1/2. Recently, this statements have been generalized to random settings. Lee and Sudakov (2012) proved that the local resilience of a random graph with edge probability p=ω(log n/n) with respect to Hamiltonicity is 1/2±o(1). For random directed graphs, Hefetz, Steger and Sudakov (2014) proved an analogue statement, but only for edge probability p=ω(log n/n). In this paper we significantly improve their result to p=ω(log8 n/n), which is optimal up to the polylogarithmic factor.

AB - In his seminal paper from 1952 Dirac showed that the complete graph on n≥3 vertices remains Hamiltonian even if we allow an adversary to remove ⌊n/2⌋ edges touching each vertex. In 1960 Ghouila-Houri obtained an analogue statement for digraphs by showing that every directed graph on n≥3 vertices with minimum in- and out-degree at least n/2 contains a directed Hamilton cycle. Both statements quantify the robustness of complete graphs (digraphs) with respect to the property of containing a Hamilton cycle.A natural way to generalize such results to arbitrary graphs (digraphs) is using the notion of local resilience. The local resilience of a graph (digraph) G with respect to a property P is the maximum number r such that G has the property P even if we allow an adversary to remove an r-fraction of (in- and out-going) edges touching each vertex. The theorems of Dirac and Ghouila-Houri state that the local resilience of the complete graph and digraph with respect to Hamiltonicity is 1/2. Recently, this statements have been generalized to random settings. Lee and Sudakov (2012) proved that the local resilience of a random graph with edge probability p=ω(log n/n) with respect to Hamiltonicity is 1/2±o(1). For random directed graphs, Hefetz, Steger and Sudakov (2014) proved an analogue statement, but only for edge probability p=ω(log n/n). In this paper we significantly improve their result to p=ω(log8 n/n), which is optimal up to the polylogarithmic factor.

KW - Directed Hamilton cycle

KW - Local resilience

KW - Random digraphs

UR - http://www.scopus.com/inward/record.url?scp=85016194777&partnerID=8YFLogxK

U2 - 10.1016/j.jctb.2017.03.006

DO - 10.1016/j.jctb.2017.03.006

M3 - Article

AN - SCOPUS:85016194777

VL - 126

SP - 1

EP - 23

JO - Journal of Combinatorial Theory, Series B

JF - Journal of Combinatorial Theory, Series B

SN - 0095-8956

ER -