{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:39:01Z","timestamp":1787323141707,"version":"build-2736575974"},"reference-count":13,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","funder":[{"DOI":"10.13039\/501100001711","name":"Schweizerischer Nationalfonds zur F\u00f6rderung der Wissenschaftlichen Forschung","doi-asserted-by":"publisher","award":["200021-175573"],"award-info":[{"award-number":["200021-175573"]}],"id":[{"id":"10.13039\/501100001711","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001711","name":"Schweizerischer Nationalfonds zur F\u00f6rderung der Wissenschaftlichen Forschung","doi-asserted-by":"publisher","award":["200021-169242"],"award-info":[{"award-number":["200021-169242"]}],"id":[{"id":"10.13039\/501100001711","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2021,1]]},"abstract":"<jats:p>A seminal result by Koml\u00f3s, Sark\u00f6zy, and Szemer\u00e9di states that if a graph $G$ with $n$ vertices has minimum degree at least $kn\/(k + 1)$, for some $k \\in \\mathbb{N}$ and $n$ sufficiently large, then it contains the $k$th power of a Hamilton cycle. This is easily seen to be the largest power of a Hamilton cycle one can guarantee, given such a minimum degree assumption. Following a recent trend of studying effects of adding random edges to a dense graph, the model known as the randomly perturbed graph, Dudek et al. showed that if the minimum degree is at least $kn\/(k + 1) + \\alpha n$, for any constant $\\alpha &gt; 0$, then adding $O(n)$ random edges on top almost surely results in a graph which contains the $(k + 1)$st power of a Hamilton cycle. We show that the effect of these random edges is significantly stronger, namely, that one can almost surely find the $(2k + 1)$st power. This is the largest power one can guarantee in such a setting.<\/jats:p>","DOI":"10.1137\/19m125412x","type":"journal-article","created":{"date-parts":[[2021,5,17]],"date-time":"2021-05-17T11:57:11Z","timestamp":1621252631000},"page":"988-1004","source":"Crossref","is-referenced-by-count":9,"title":["Sprinkling a Few Random Edges Doubles the Power"],"prefix":"10.1137","volume":"35","author":[{"given":"Rajko","family":"Nenadov","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Milo\u0161","family":"Truji\u0107","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2021,5,17]]},"reference":[{"key":"atypb1","doi-asserted-by":"crossref","unstructured":"J. A. Bondy and U. S. R. Murty,\n                      Graph Theory\n                      , 1st ed., Grad. Texts Math. 244, Springer, New York, 2008.","DOI":"10.1007\/978-1-84628-970-5"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1112\/plms\/s3-2.1.69"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20870"},{"key":"atypb4","unstructured":"P. Erd\u00f6s,\n                      Problem\n                      9, in Theory of Graphs and Its Applications, M. Fieldler, ed., Publishing House of the Czechosovak Academy of Sciences, Prague, 1964, p. 159."},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(91)90007-7"},{"key":"atypb6","first-page":"601","volume":"2","author":"Hajnal A.","year":"1970","journal-title":"Combin. Theory Appl."},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1007\/BF01626028"},{"key":"atypb8","unstructured":"J. Koml\u00f3s and M. Simonovits,\n                      Szemer\u00e9di's regularity lemma and its applications in graph theory\n                      , in Combinatorics, Paul Erd\u00f6s is Eighty, Vol. 2, Keszthely, 1993, Bolyai Soc. Math. Stud. 2, J\u00e1nos Bolyai Mathematical Society, Budapest, 1996, pp. 295-352."},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548397003106"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548305007042"},{"key":"atypb11","first-page":"287","author":"R\u00f6dl V.","year":"2010","journal-title":"Berlin"},{"key":"atypb12","first-page":"201","author":"Seymour P.","year":"1973","journal-title":"Cambridge"},{"key":"atypb13","first-page":"399","author":"Szemer\u00e9di E.","year":"1978","journal-title":"Paris"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/19M125412X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:44:16Z","timestamp":1787319856000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/19M125412X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1]]},"references-count":13,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2021,1]]}},"alternative-id":["10.1137\/19M125412X"],"URL":"https:\/\/doi.org\/10.1137\/19m125412x","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,1]]}}}