Sie können Bookmarks mittels Listen verwalten, loggen Sie sich dafür bitte in Ihr SLUB Benutzerkonto ein.
Medientyp:
E-Artikel
Titel:
Hamiltonicity in random directed graphs is born resilient
Beteiligte:
Montgomery, Richard
Erschienen:
Cambridge University Press (CUP), 2020
Erschienen in:
Combinatorics, Probability and Computing, 29 (2020) 6, Seite 900-942
Sprache:
Englisch
DOI:
10.1017/s0963548320000140
ISSN:
0963-5483;
1469-2163
Entstehung:
Anmerkungen:
Beschreibung:
AbstractLet$\{D_M\}_{M\geq 0}$be then-vertex random directed graph process, where$D_0$is the empty directed graph onnvertices, 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)$.