{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:04:46Z","timestamp":1787321086862,"version":"build-2736575974"},"reference-count":42,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["PA 3513\/1-1"],"award-info":[{"award-number":["PA 3513\/1-1"]}],"id":[{"id":"10.13039\/501100001659","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>Maker-Breaker games are played on a hypergraph $(X,\\mathcal{F})$, where $\\mathcal{F} \\subseteq 2^X$ denotes the family of winning sets. Both players alternately claim a predefined amount of edges (called bias) from the board $X$, and Maker wins the game if she is able to occupy any winning set $F \\in \\mathcal{F}$. These games are well studied when played on the complete graph $K_n$ or on a random graph $G_{n,p}$. In this paper we consider Maker-Breaker games played on randomly perturbed graphs instead. These graphs consist of the union of a deterministic graph $G_\\alpha$ with minimum degree at least $\\alpha n$ and a binomial random graph $G_{n,p}$. Depending on $\\alpha$ and Breaker's bias $b$ we determine the order of the threshold probability for winning the Hamiltonicity game and the $k$-connectivity game on $G_{\\alpha}\\cup G_{n,p}$, and we discuss the $H$-game when $b=1$.<\/jats:p>","DOI":"10.1137\/20m1385044","type":"journal-article","created":{"date-parts":[[2021,11,15]],"date-time":"2021-11-15T11:12:25Z","timestamp":1636974745000},"page":"2723-2748","source":"Crossref","is-referenced-by-count":2,"title":["Maker-Breaker Games on Randomly Perturbed Graphs"],"prefix":"10.1137","volume":"35","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5940-6556","authenticated-orcid":true,"given":"Dennis","family":"Clemens","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Fabian","family":"Hamann","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4239-9112","authenticated-orcid":true,"given":"Yannick","family":"Mogge","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6419-8560","authenticated-orcid":true,"given":"Olaf","family":"Parczyk","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2021,11,15]]},"reference":[{"key":"atypb1","unstructured":"P. Allen, J. B\u00f6ttcher, Y. Kohayakawa, H. Naves, and Y. Person,\n                      Making Spanning Graphs\n                      , preprint,arXiv:1711.05311, 2017."},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548310000064"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548318000366"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1007\/BF01897304"},{"key":"atypb5","doi-asserted-by":"crossref","unstructured":"J. Beck,\n                      Combinatorial Games: Tic-Tac-Toe Theory\n                      , Encyclopedia Math. Appl. 114, Cambridge University Press, Cambridge, UK, 2008.","DOI":"10.1017\/CBO9780511735202"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1007\/s004930070002"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20392"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10112"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10070"},{"key":"atypb10","doi-asserted-by":"crossref","unstructured":"B. Bollob\u00e1s,\n                      Random Graphs\n                      , Cambridge University Press, Cambridge, UK, 2001.","DOI":"10.1017\/CBO9780511814068"},{"key":"atypb11","first-page":"35","author":"Bollob\u00e1s B.","year":"1984","journal-title":"London"},{"key":"atypb12","first-page":"221","author":"Chv\u00e1tal V.","year":"1978","journal-title":"Amsterdam"},{"key":"atypb13","doi-asserted-by":"crossref","unstructured":"S. Das and A. Treglown,\n                      Ramsey properties of randomly perturbed graphs: Cliques and cycles\n                      , Combin., Probab. Comput. (2020), pp. 1-38.","DOI":"10.1017\/S0963548320000231"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1112\/plms\/s3-2.1.69"},{"key":"atypb15","first-page":"601","author":"Hajnal A.","year":"1970","journal-title":"Budapest"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1007\/BF02066689"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9904-1946-08715-7"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20528"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20619"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20344"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20279"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20981"},{"key":"atypb23","doi-asserted-by":"crossref","unstructured":"D. Hefetz, M. Krivelevich, M. Stojakovi\u0107, and T. Szab\u00f3,\n                      Positional Games\n                      , Birkh\u00e4user, Basel, 2014.","DOI":"10.1007\/978-3-0348-0825-5"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20252"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2006.03.004"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-009-2362-0"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1963.10500830"},{"key":"atypb28","doi-asserted-by":"crossref","unstructured":"S. Janson, T. \u0141uczak, and A. Ruci\u0144ski,\n                      Random Graphs\n                      , Wiley, New York, 2000.","DOI":"10.1002\/9781118032718"},{"key":"atypb29","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20224"},{"key":"atypb30","unstructured":"D. Karger,\n                      Global min-cuts and other ramifications of a simple min-cut algorithm\n                      , in Proceedings of the 4th Annual ACM-SIAM Symposium on Discrete Algorithms, 1993, pp. 21-30."},{"key":"atypb31","first-page":"295","author":"Koml\u00f3s J.","year":"1996","journal-title":"Budapest"},{"key":"atypb32","first-page":"529","volume":"228","author":"Korshunov A. D.","year":"1976","journal-title":"Dokl. Akad. Nauk"},{"key":"atypb33","doi-asserted-by":"publisher","DOI":"10.1090\/S0894-0347-2010-00678-9"},{"key":"atypb34","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-2014-05963-1"},{"key":"atypb35","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20097"},{"key":"atypb36","unstructured":"A. Liebenau and R. Nenadov,\n                      The Threshold Bias of the Clique-Factor Game\n                      , preprint, arXiv:2002.02578, 2020."},{"key":"atypb37","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20489"},{"key":"atypb38","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20628"},{"key":"atypb39","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(76)90068-6"},{"key":"atypb40","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20059"},{"key":"atypb41","first-page":"436","author":"Tur\u00e1n P.","year":"1941","journal-title":"Mat. Fiz. Lapok (48) ("},{"key":"atypb42","unstructured":"D. B. West,\n                      Introduction to Graph Theory\n                      , Prentice Hall, Hoboken, NJ, 2001."}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/20M1385044","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:06:47Z","timestamp":1787317607000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/20M1385044"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1]]},"references-count":42,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2021,1]]}},"alternative-id":["10.1137\/20M1385044"],"URL":"https:\/\/doi.org\/10.1137\/20m1385044","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,1]]}}}