Hamiltonicity in random directed graphs is born resilient

Abstract

Let $\{D_M{\}}_{M\ge 0}$ be the $n$-vertex random directed graph process, where $D_0$ is the empty directed graph on $n$ vertices, and subsequent directed graphs in the sequence are obtained by the addition of a new directed edge uniformly at random. For each $\epsilon >0$, we show that, almost surely, any directed graph $D_M$ with minimum in- and out-degree at least 1 is not only Hamiltonian (as shown by Frieze), but remains Hamiltonian when edges are removed, as long as at most $(1/2-\epsilon )$ of both the in- and out-edges incident to each vertex are removed. We say such a directed graph is $(1/2-\epsilon )$-resiliently Hamiltonian. Furthermore, for each $\epsilon >0$, we show that, almost surely, each directed graph $D_M$ in the sequence is not $(1/2+\epsilon )$-resiliently Hamiltonian. This improves a result of Ferber, Nenadov, Noever, Peter and Škorić, who showed, for each $\epsilon >0$, that the binomial random directed graph $D(n,p)$ is almost surely $(1/2-\epsilon )$-resiliently Hamiltonian if $p=\omega ({\log }^{8}n/n)$.

36 pages, 2 figures. Updated to accepted version