{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,5]],"date-time":"2026-02-05T21:03:02Z","timestamp":1770325382141,"version":"3.49.0"},"reference-count":40,"publisher":"Cambridge University Press (CUP)","issue":"2","license":[{"start":{"date-parts":[[2010,12,16]],"date-time":"2010-12-16T00:00:00Z","timestamp":1292457600000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2011,3]]},"abstract":"<jats:p>For an increasing monotone graph property<jats:private-char><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" mimetype=\"image\" xlink:type=\"simple\" xlink:href=\"S0963548310000453_char1\"\/><\/jats:private-char>the<jats:italic>local resilience<\/jats:italic>of a graph<jats:italic>G<\/jats:italic>with respect to<jats:private-char><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" mimetype=\"image\" xlink:type=\"simple\" xlink:href=\"S0963548310000453_char1\"\/><\/jats:private-char>is the minimal<jats:italic>r<\/jats:italic>for which there exists a subgraph<jats:italic>H<\/jats:italic>\u2286<jats:italic>G<\/jats:italic>with all degrees at most<jats:italic>r<\/jats:italic>, such that the removal of the edges of<jats:italic>H<\/jats:italic>from<jats:italic>G<\/jats:italic>creates a graph that does not possess<jats:private-char><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" mimetype=\"image\" xlink:type=\"simple\" xlink:href=\"S0963548310000453_char1\"\/><\/jats:private-char>. This notion, which was implicitly studied for some<jats:italic>ad hoc<\/jats:italic>properties, was recently treated in a more systematic way in a paper by Sudakov and Vu. Most research conducted with respect to this distance notion focused on the binomial random graph model<jats:private-char><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" mimetype=\"image\" xlink:type=\"simple\" xlink:href=\"S0963548310000453_char2\"\/><\/jats:private-char>(<jats:italic>n, p<\/jats:italic>) and some families of pseudo-random graphs with respect to several graph properties, such as containing a perfect matching and being Hamiltonian, to name a few. In this paper we continue to explore the local resilience notion, but turn our attention to random and pseudo-random<jats:italic>regular<\/jats:italic>graphs of constant degree. We investigate the local resilience of the typical random<jats:italic>d<\/jats:italic>-regular graph with respect to edge and vertex connectivity, containing a perfect matching, and being Hamiltonian. In particular, we prove that for every positive \u03f5 and large enough values of<jats:italic>d<\/jats:italic>, with high probability, the local resilience of the random<jats:italic>d<\/jats:italic>-regular graph,<jats:private-char><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" mimetype=\"image\" xlink:type=\"simple\" xlink:href=\"S0963548310000453_char2\"\/><\/jats:private-char><jats:sub><jats:italic>n, d<\/jats:italic><\/jats:sub>, with respect to being Hamiltonian, is at least (1\u2212\u03f5)<jats:italic>d<\/jats:italic>\/6. We also prove that for the binomial random graph model<jats:private-char><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" mimetype=\"image\" xlink:type=\"simple\" xlink:href=\"S0963548310000453_char2\"\/><\/jats:private-char>(<jats:italic>n, p<\/jats:italic>), for every positive \u03f5 &gt; 0 and large enough values of<jats:italic>K<\/jats:italic>, if<jats:italic>p<\/jats:italic>&gt;<jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" mimetype=\"image\" xlink:type=\"simple\" xlink:href=\"S0963548310000453_inline1\"><jats:alt-text>$\\frac{K\\ln n}{n}$<\/jats:alt-text><\/jats:inline-graphic>then, with high probability, the local resilience of<jats:private-char><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" mimetype=\"image\" xlink:type=\"simple\" xlink:href=\"S0963548310000453_char2\"\/><\/jats:private-char>(<jats:italic>n, p<\/jats:italic>) with respect to being Hamiltonian is at least (1\u2212\u03f5)<jats:italic>np<\/jats:italic>\/6. Finally, we apply similar techniques to positional games, and prove that if<jats:italic>d<\/jats:italic>is large enough then, with high probability, a typical random<jats:italic>d<\/jats:italic>-regular graph<jats:italic>G<\/jats:italic>is such that, in the unbiased Maker\u2013Breaker game played on the edges of<jats:italic>G<\/jats:italic>, Maker has a winning strategy to create a Hamilton cycle.<\/jats:p>","DOI":"10.1017\/s0963548310000453","type":"journal-article","created":{"date-parts":[[2011,1,5]],"date-time":"2011-01-05T09:06:46Z","timestamp":1294218406000},"page":"173-211","source":"Crossref","is-referenced-by-count":23,"title":["Local Resilience and Hamiltonicity Maker\u2013Breaker Games in Random Regular Graphs"],"prefix":"10.1017","volume":"20","author":[{"given":"SONNY","family":"BEN-SHIMON","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"MICHAEL","family":"KRIVELEVICH","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"BENNY","family":"SUDAKOV","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2010,12,16]]},"reference":[{"key":"S0963548310000453_ref34","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(76)90068-6"},{"key":"S0963548310000453_ref33","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(91)90112-F"},{"key":"S0963548310000453_ref14","doi-asserted-by":"publisher","DOI":"10.1007\/s11856-008-1028-8"},{"key":"S0963548310000453_ref10","volume-title":"Graduate Texts in Mathematics","author":"Diestel","year":"2005"},{"key":"S0963548310000453_ref40","first-page":"239","volume-title":"Surveys in Combinatorics","author":"Wormald","year":"1999"},{"key":"S0963548310000453_ref6","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795290805"},{"key":"S0963548310000453_ref23","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2006.09.032"},{"key":"S0963548310000453_ref17","unstructured":"[17] Hefetz D. , Krivelevich M. , Stojakovi\u0107 M. and Szab\u00f3 T. Global Maker-Breaker games on sparse graphs. Europ. J. Combin., to appear."},{"key":"S0963548310000453_ref12","article-title":"A proof of Alon's second eigenvalue conjecture and related problems","volume":"195","author":"Friedman","year":"2008","journal-title":"Mem. Amer. Math. Soc."},{"key":"S0963548310000453_ref1","doi-asserted-by":"publisher","DOI":"10.1002\/9780470277331"},{"key":"S0963548310000453_ref4","doi-asserted-by":"publisher","DOI":"10.1016\/S0195-6698(83)80039-0"},{"key":"S0963548310000453_ref30","doi-asserted-by":"publisher","DOI":"10.1137\/0112059"},{"key":"S0963548310000453_ref25","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.2000.1991"},{"key":"S0963548310000453_ref3","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511662157.006"},{"key":"S0963548310000453_ref29","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.1013"},{"key":"S0963548310000453_ref19","doi-asserted-by":"crossref","first-page":"R28","DOI":"10.37236\/117","article-title":"On two problems regarding the Hamilton cycle game","volume":"16","author":"Hefetz","year":"2009","journal-title":"Electron. J. Combin."},{"key":"S0963548310000453_ref28","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-32439-3_10"},{"key":"S0963548310000453_ref39","doi-asserted-by":"publisher","DOI":"10.1016\/S0095-8956(81)80021-4"},{"key":"S0963548310000453_ref20","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548300001735"},{"key":"S0963548310000453_ref18","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-009-2362-0"},{"key":"S0963548310000453_ref31","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-12788-9_6"},{"key":"S0963548310000453_ref13","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(88)90089-5"},{"key":"S0963548310000453_ref7","volume-title":"Surveys in Differential Geometry: Eigenvalues of Laplacians and Other Geometric Operators","author":"Chung","year":"2004"},{"key":"S0963548310000453_ref5","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511814068"},{"key":"S0963548310000453_ref27","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.10065"},{"key":"S0963548310000453_ref8","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-5060(08)70335-2"},{"key":"S0963548310000453_ref32","first-page":"15","article-title":"Asymptotics for symmetric 0\u20131 matrices with prescribed row sums.","volume":"19","author":"McKay","year":"1985","journal-title":"Ars Combinatorica"},{"key":"S0963548310000453_ref16","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20252"},{"key":"S0963548310000453_ref35","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240030202"},{"key":"S0963548310000453_ref15","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548301005065"},{"key":"S0963548310000453_ref24","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2003.10.007"},{"key":"S0963548310000453_ref36","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240050209"},{"key":"S0963548310000453_ref21","doi-asserted-by":"publisher","DOI":"10.1002\/9781118032718"},{"key":"S0963548310000453_ref26","doi-asserted-by":"publisher","DOI":"10.1137\/090761148"},{"key":"S0963548310000453_ref9","doi-asserted-by":"crossref","first-page":"R32","DOI":"10.37236\/756","article-title":"On the resilience of long cycles in random graphs","volume":"15","author":"Dellamonica","year":"2008","journal-title":"Electron. J. Combin."},{"key":"S0963548310000453_ref22","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10054"},{"key":"S0963548310000453_ref37","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20235"},{"key":"S0963548310000453_ref2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511735202"},{"key":"S0963548310000453_ref11","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(84)90066-2"},{"key":"S0963548310000453_ref38","first-page":"436","article-title":"Eine Extremalaufgabe aus der Graphentheorie.","volume":"48","author":"Tur\u00e1n","year":"1941","journal-title":"Mat. Fiz. Lapok"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548310000453","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,6,15]],"date-time":"2020-06-15T08:31:39Z","timestamp":1592209899000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548310000453\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,12,16]]},"references-count":40,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2011,3]]}},"alternative-id":["S0963548310000453"],"URL":"https:\/\/doi.org\/10.1017\/s0963548310000453","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,12,16]]}}}