{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,8]],"date-time":"2026-03-08T22:36:28Z","timestamp":1773009388493,"version":"3.50.1"},"reference-count":31,"publisher":"Cambridge University Press (CUP)","issue":"6","license":[{"start":{"date-parts":[[2020,6,24]],"date-time":"2020-06-24T00:00:00Z","timestamp":1592956800000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2020,11]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Let<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548320000140_inline1.png\"\/><jats:tex-math>$\\{D_M\\}_{M\\geq 0}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>be the<jats:italic>n<\/jats:italic>-vertex random directed graph process, where<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548320000140_inline2.png\"\/><jats:tex-math>$D_0$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>is the empty directed graph on<jats:italic>n<\/jats:italic>vertices, and subsequent directed graphs in the sequence are obtained by the addition of a new directed edge uniformly at random. For each<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548320000140_inline3.png\"\/><jats:tex-math>$$\\varepsilon &gt; 0$$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, we show that, almost surely, any directed graph<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548320000140_inline4.png\"\/><jats:tex-math>$D_M$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>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<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548320000140_inline5.png\"\/><jats:tex-math>$1\/2-\\varepsilon$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>of both the in- and out-edges incident to each vertex are removed. We say such a directed graph is<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548320000140_inline6.png\"\/><jats:tex-math>$(1\/2-\\varepsilon)$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>-<jats:italic>resiliently Hamiltonian<\/jats:italic>. Furthermore, for each<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548320000140_inline7.png\"\/><jats:tex-math>$\\varepsilon &gt; 0$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, we show that, almost surely, each directed graph<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548320000140_inline8.png\"\/><jats:tex-math>$D_M$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>in the sequence is not<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548320000140_inline9.png\"\/><jats:tex-math>$(1\/2+\\varepsilon)$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>-resiliently Hamiltonian.<\/jats:p><jats:p>This improves a result of Ferber, Nenadov, Noever, Peter and \u0160kori\u0107 who showed, for each<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548320000140_inline10.png\"\/><jats:tex-math>$\\varepsilon &gt; 0$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, that the binomial random directed graph<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548320000140_inline11.png\"\/><jats:tex-math>$D(n,p)$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>is almost surely<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548320000140_inline12.png\"\/><jats:tex-math>$(1\/2-\\varepsilon)$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>-resiliently Hamiltonian if<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548320000140_inline13.png\"\/><jats:tex-math>$p=\\omega(\\log^8n\/n)$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>.<\/jats:p>","DOI":"10.1017\/s0963548320000140","type":"journal-article","created":{"date-parts":[[2020,6,24]],"date-time":"2020-06-24T08:47:42Z","timestamp":1592988462000},"page":"900-942","update-policy":"https:\/\/doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":7,"title":["Hamiltonicity in random directed graphs is born resilient"],"prefix":"10.1017","volume":"29","author":[{"given":"Richard","family":"Montgomery","sequence":"first","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2020,6,24]]},"reference":[{"key":"S0963548320000140_ref20","first-page":"760","article-title":"Solution of a problem of Erd\u0151s and R\u00e9nyi on Hamilton cycles in non-oriented graphs","volume":"17","author":"Korshunov","year":"1976","journal-title":"Soviet Math. Dokl."},{"key":"S0963548320000140_ref7","unstructured":"[7] Bollob\u00e1s, B. (1984) The evolution of sparse graphs. In Graph Theory and Combinatorics: Cambridge Combinatorial Conference in Honour of Paul Erd\u0151s, pp. 335\u2013357, Academic Press."},{"key":"S0963548320000140_ref22","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20419"},{"key":"S0963548320000140_ref29","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(77)90044-9"},{"key":"S0963548320000140_ref5","doi-asserted-by":"publisher","DOI":"10.1137\/110821299"},{"key":"S0963548320000140_ref8","unstructured":"[8] Dirac, G. (1952) Some theorems on abstract graphs. Proc. London Math. Soc. 3 69\u201381."},{"key":"S0963548320000140_ref1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-0208(08)73007-X"},{"key":"S0963548320000140_ref30","first-page":"372","volume-title":"Series","author":"Sudakov","year":"2017"},{"key":"S0963548320000140_ref27","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(76)90068-6"},{"key":"S0963548320000140_ref26","unstructured":"[26] Pittel, B. (1982) On the probable behaviour of some algorithms for finding the stability number of a graph. Math. Proc. Cambridge Philos. Soc. 92 511\u2013526."},{"key":"S0963548320000140_ref23","doi-asserted-by":"publisher","DOI":"10.2307\/1426987"},{"key":"S0963548320000140_ref13","doi-asserted-by":"publisher","DOI":"10.1007\/s11856-008-1028-8"},{"key":"S0963548320000140_ref11","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2017.03.006"},{"key":"S0963548320000140_ref21","doi-asserted-by":"publisher","DOI":"10.1137\/090761148"},{"key":"S0963548320000140_ref10","first-page":"455","article-title":"On random matrices","volume":"8","author":"Erd\u0151s","year":"1964","journal-title":"Magyar Tud. Akad. Mat. Kutat\u00f3 Int. K\u00f6zl"},{"key":"S0963548320000140_ref17","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20631"},{"key":"S0963548320000140_ref19","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(83)90021-3"},{"key":"S0963548320000140_ref4","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20345"},{"key":"S0963548320000140_ref12","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(88)90037-5"},{"key":"S0963548320000140_ref24","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2019.04.002"},{"key":"S0963548320000140_ref9","doi-asserted-by":"crossref","first-page":"290","DOI":"10.5486\/PMD.1959.6.3-4.12","article-title":"On random graphs I","volume":"6","author":"Erd\u0151s","year":"1959","journal-title":"Publ. Math. Debrecen"},{"key":"S0963548320000140_ref18","volume-title":"Random Graphs","author":"Janson","year":"2011"},{"key":"S0963548320000140_ref2","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-007-2182-z"},{"key":"S0963548320000140_ref3","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.21995"},{"key":"S0963548320000140_ref6","doi-asserted-by":"publisher","DOI":"10.1016\/S0195-6698(83)80039-0"},{"key":"S0963548320000140_ref31","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20235"},{"key":"S0963548320000140_ref25","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20827"},{"key":"S0963548320000140_ref16","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20472"},{"key":"S0963548320000140_ref28","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-008-2295-z"},{"key":"S0963548320000140_ref14","first-page":"495","article-title":"Une condition suffisante d\u2019existence d\u2019un circuit Hamiltonien","volume":"251","author":"Ghouila-Houri","year":"1960","journal-title":"CR Acad. Sci. Paris"},{"key":"S0963548320000140_ref15","unstructured":"[15] Glebov, R. (2013) On Hamilton cycles and other spanning structures. PhD thesis."}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548320000140","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,2]],"date-time":"2023-10-02T21:37:09Z","timestamp":1696282629000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548320000140\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,24]]},"references-count":31,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2020,11]]}},"alternative-id":["S0963548320000140"],"URL":"https:\/\/doi.org\/10.1017\/s0963548320000140","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,6,24]]},"assertion":[{"value":"\u00a9 The Author(s), 2020. Published by Cambridge University Press","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}}]}}