{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,8,3]],"date-time":"2024-08-03T09:16:38Z","timestamp":1722676598779},"reference-count":38,"publisher":"Cambridge University Press (CUP)","issue":"1","license":[{"start":{"date-parts":[[2020,8,28]],"date-time":"2020-08-28T00:00:00Z","timestamp":1598572800000},"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":[[2021,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We prove a \u2018resilience\u2019 version of Dirac\u2019s theorem in the setting of random regular graphs. More precisely, we show that whenever <jats:italic>d<\/jats:italic> is sufficiently large compared to <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548320000346_inline1.png\" \/><jats:tex-math>\n$\\epsilon &gt; 0$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, a.a.s. the following holds. Let <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548320000346_inline2.png\" \/><jats:tex-math>\n$G'$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> be any subgraph of the random <jats:italic>n<\/jats:italic>-vertex <jats:italic>d<\/jats:italic>-regular graph <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548320000346_inline3.png\" \/><jats:tex-math>\n$G_{n,d}$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> with minimum degree at least <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548320000346_inline4.png\" \/><jats:tex-math>\n$$(1\/2 + \\epsilon )d$$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>. Then <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548320000346_inline5.png\" \/><jats:tex-math>\n$G'$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> is Hamiltonian.<\/jats:p><jats:p>This proves a conjecture of Ben-Shimon, Krivelevich and Sudakov. Our result is best possible: firstly the condition that <jats:italic>d<\/jats:italic> is large cannot be omitted, and secondly the minimum degree bound cannot be improved.<\/jats:p>","DOI":"10.1017\/s0963548320000346","type":"journal-article","created":{"date-parts":[[2020,8,28]],"date-time":"2020-08-28T07:55:38Z","timestamp":1598601338000},"page":"17-36","update-policy":"http:\/\/dx.doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":2,"title":["Dirac\u2019s theorem for random regular graphs"],"prefix":"10.1017","volume":"30","author":[{"given":"Padraig","family":"Condon","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alberto","family":"Espuny D\u00edaz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ant\u00f3nio","family":"Gir\u00e3o","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Daniela","family":"K\u00fchn","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Deryk","family":"Osthus","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2020,8,28]]},"reference":[{"key":"S0963548320000346_ref5","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1002\/rsa.20345","article-title":"Local resilience of almost spanning trees in random graphs","volume":"38","author":"Balogh","year":"2011","journal-title":"Random Struct. Algorithms"},{"key":"S0963548320000346_ref7","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548310000453"},{"key":"S0963548320000346_ref12","unstructured":"[12] Condon, P. , Espuny Daz, A. , Kim, J. , K\u00fchn, D. and Osthus, D. (2019) Resilient degree sequences with respect to Hamilton cycles and matchings in random graphs. Electron. J. Combin. 26 4.54."},{"key":"S0963548320000346_ref38","first-page":"239","volume-title":"Series","author":"Wormald","year":"1999"},{"key":"S0963548320000346_ref1","first-page":"173","volume-title":"Studies","author":"Ajtai","year":"1985"},{"key":"S0963548320000346_ref30","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2019.04.002"},{"key":"S0963548320000346_ref11","unstructured":"[11] Condon, P. , Espuny D\u00edaz, A. , Gir\u00e3o, A. , K\u00fchn, D. and Osthus, D. (2019) Dirac\u2019s theorem for random regular graphs. arXiv:1903.05052"},{"key":"S0963548320000346_ref17","doi-asserted-by":"publisher","DOI":"10.1007\/s11856-008-1028-8"},{"key":"S0963548320000346_ref14","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548301005090"},{"key":"S0963548320000346_ref21","doi-asserted-by":"publisher","DOI":"10.1002\/9781118032718"},{"key":"S0963548320000346_ref32","doi-asserted-by":"crossref","first-page":"797","DOI":"10.1002\/rsa.20827","article-title":"Resilience of perfect matchings and Hamiltonicity in random graph processes","volume":"54","author":"Nenadov","year":"2019","journal-title":"Random Struct. Algorithms"},{"key":"S0963548320000346_ref9","doi-asserted-by":"crossref","first-page":"311","DOI":"10.1016\/S0195-6698(80)80030-8","article-title":"A probabilistic proof of an asymptotic formula for the number of labelled regular graphs","volume":"1","author":"Bollob\u00e1s","year":"1980","journal-title":"European J. Combin."},{"key":"S0963548320000346_ref8","doi-asserted-by":"crossref","first-page":"1176","DOI":"10.1137\/110821299","article-title":"On the resilience of Hamiltonicity and optimal packing of Hamilton cycles in random graphs","volume":"25","author":"Ben-Shimon","year":"2011","journal-title":"SIAM J. Discrete Math."},{"key":"S0963548320000346_ref24","doi-asserted-by":"crossref","unstructured":"[24] Krivelevich, M. (2016) Long paths and Hamiltonicity in random graphs. In Random Graphs, Geometry and Asymptotic Structure ( Fountoulakis, N. and Hefetz, D. , eds), Vol. 84 of London Mathematical Society Student Texts, pp. 4\u201327. Cambridge University Press.","DOI":"10.1017\/CBO9781316479988.002"},{"key":"S0963548320000346_ref3","unstructured":"[3] Alon, N. and Spencer, J. H. (2016) The Probabilistic Method, Wiley Series in Discrete Mathematics and Optimization. Wiley."},{"key":"S0963548320000346_ref20","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2011.03.002"},{"key":"S0963548320000346_ref35","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20817"},{"key":"S0963548320000346_ref31","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548320000140"},{"key":"S0963548320000346_ref13","doi-asserted-by":"publisher","DOI":"10.1214\/17-AOP1180"},{"key":"S0963548320000346_ref10","unstructured":"[10] Bollob\u00e1s, B. (1984) The evolution of sparse graphs. In Graph Theory and Combinatorics (Cambridge, 1983), pp. 35\u201357. Academic Press."},{"key":"S0963548320000346_ref6","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548311000642"},{"key":"S0963548320000346_ref2","doi-asserted-by":"publisher","DOI":"10.19086\/aic.12849"},{"key":"S0963548320000346_ref33","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240030202"},{"key":"S0963548320000346_ref23","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(83)90021-3"},{"key":"S0963548320000346_ref18","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20631"},{"key":"S0963548320000346_ref34","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240050209"},{"key":"S0963548320000346_ref22","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2003.10.007"},{"key":"S0963548320000346_ref26","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.1013"},{"key":"S0963548320000346_ref16","unstructured":"[16] Frieze, A. (2019) Hamilton cycles in random graphs: a bibliography. arXiv:1901.07139"},{"key":"S0963548320000346_ref15","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2017.03.006"},{"key":"S0963548320000346_ref36","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20235"},{"key":"S0963548320000346_ref19","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1963.10500830"},{"key":"S0963548320000346_ref25","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1137\/090761148","article-title":"Resilient pancyclicity of random and pseudorandom graphs","volume":"24","author":"Krivelevich","year":"2010","journal-title":"SIAM J. Discrete Math."},{"key":"S0963548320000346_ref27","doi-asserted-by":"crossref","first-page":"293","DOI":"10.1002\/rsa.20419","article-title":"Dirac\u2019s theorem for random graphs","volume":"41","author":"Lee","year":"2012","journal-title":"Random Struct. Algorithms"},{"key":"S0963548320000346_ref4","doi-asserted-by":"publisher","DOI":"10.2748\/tmj\/1178243286"},{"key":"S0963548320000346_ref37","doi-asserted-by":"crossref","first-page":"362","DOI":"10.1214\/18-AOP1263","article-title":"The spectral gap of dense random regular graphs","volume":"47","author":"Tikhomirov","year":"2019","journal-title":"Ann. Probab."},{"key":"S0963548320000346_ref29","doi-asserted-by":"crossref","first-page":"52","DOI":"10.1016\/0196-6774(90)90029-E","article-title":"Uniform generation of random regular graphs of moderate degree","volume":"11","author":"McKay","year":"1990","journal-title":"J. Algorithms"},{"key":"S0963548320000346_ref28","first-page":"179","article-title":"Independent sets in regular graphs of high girth","volume":"23","author":"McKay","year":"1987","journal-title":"Ars Combin."}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548320000346","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,1,21]],"date-time":"2021-01-21T11:51:21Z","timestamp":1611229881000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548320000346\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,8,28]]},"references-count":38,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,1]]}},"alternative-id":["S0963548320000346"],"URL":"https:\/\/doi.org\/10.1017\/s0963548320000346","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,8,28]]},"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"}}]}}