Hamiltonicity in random directed graphs is born resilient. (24th November 2020)

• Record Type: Journal Article
• Authors: Montgomery, Richard
• Is Part Of: Combinatorics, probability and computing. Volume 29:Number 6(2020)
• Page Start: 900
• Page End: 942
• Publication Date: 2020-11-24
• Subjects: 05C20, -- 05C80, -- 05C38, -- 05C45; Combinatorial analysis -- Periodicals; Probabilities -- Periodicals; Computer science -- Mathematics -- Periodicals; 511.6
• DOI: 10.1017/S0963548320000140
• Languages: English
• ISSNs: 0963-5483

Abstract

Abstract: Let $\{D_M\}_{M\geq 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 $$\varepsilon > 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-\varepsilon$ of both the in- and out-edges incident to each vertex are removed. We say such a directed graph is $(1/2-\varepsilon)$ - resiliently Hamiltonian . Furthermore, for each $\varepsilon > 0$, we show that, almost surely, each directed graph $D_M$ in the sequence is not $(1/2+\varepsilon)$ -resiliently Hamiltonian. This improves a result of Ferber, Nenadov, Noever, Peter and Škorić who showed, for each $\varepsilon > 0$, that the binomial random directed graph $D(n, p)$ is almost surely $(1/2-\varepsilon)$ -resiliently Hamiltonian if $p=\omega(\log^8n/n)$ .