{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,20]],"date-time":"2026-03-20T04:24:15Z","timestamp":1773980655193,"version":"3.50.1"},"reference-count":30,"publisher":"Cambridge University Press (CUP)","issue":"1","license":[{"start":{"date-parts":[[2022,7,5]],"date-time":"2022-07-05T00:00:00Z","timestamp":1656979200000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2023,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We study the problem of finding pairwise vertex-disjoint triangles in the randomly perturbed graph model, which is the union of any <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548322000153_inline1.png\"\/><jats:tex-math>\n$n$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>-vertex graph <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548322000153_inline2.png\"\/><jats:tex-math>\n$G$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> satisfying a given minimum degree condition and the binomial random graph <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548322000153_inline3.png\"\/><jats:tex-math>\n$G(n,p)$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>. We prove that asymptotically almost surely <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548322000153_inline4.png\"\/><jats:tex-math>\n$G \\cup G(n,p)$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> contains at least <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548322000153_inline5.png\"\/><jats:tex-math>\n$\\min \\{\\delta (G), \\lfloor n\/3 \\rfloor \\}$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> pairwise vertex-disjoint triangles, provided <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548322000153_inline6.png\"\/><jats:tex-math>\n$p \\ge C \\log n\/n$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, where <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548322000153_inline7.png\"\/><jats:tex-math>\n$C$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> is a large enough constant. This is a perturbed version of an old result of Dirac.<\/jats:p><jats:p>Our result is asymptotically optimal and answers a question of Han, Morris, and Treglown [RSA, 2021, no. 3, 480\u2013516] in a strong form. We also prove a stability version of our result, which in the case of pairwise vertex-disjoint triangles extends a result of Han, Morris, and Treglown [RSA, 2021, no. 3, 480\u2013516]. Together with a result of Balogh, Treglown, and Wagner [CPC, 2019, no. 2, 159\u2013176], this fully resolves the existence of triangle factors in randomly perturbed graphs.<\/jats:p><jats:p>We believe that the methods introduced in this paper are useful for a variety of related problems: we discuss possible generalisations to clique factors, cycle factors, and <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548322000153_inline8.png\"\/><jats:tex-math>\n$2$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>-universality.<\/jats:p>","DOI":"10.1017\/s0963548322000153","type":"journal-article","created":{"date-parts":[[2022,7,5]],"date-time":"2022-07-05T07:10:08Z","timestamp":1657005008000},"page":"91-121","update-policy":"https:\/\/doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":9,"title":["Triangles in randomly perturbed graphs"],"prefix":"10.1017","volume":"32","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4104-3635","authenticated-orcid":false,"given":"Julia","family":"B\u00f6ttcher","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6419-8560","authenticated-orcid":false,"given":"Olaf","family":"Parczyk","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0629-5431","authenticated-orcid":false,"given":"Amedeo","family":"Sgueglia","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3996-7676","authenticated-orcid":false,"given":"Jozef","family":"Skokan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2022,7,5]]},"reference":[{"key":"S0963548322000153_ref5","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20885"},{"key":"S0963548322000153_ref9","first-page":"404","article-title":"Cycle factors in randomly perturbed graphs","volume":"195","author":"B\u00f6ttcher","year":"2021","journal-title":"Proc. XI Latin Amer. Algor. Graphs Optim. Symp. Proc. Comput. Sci"},{"key":"S0963548322000153_ref12","doi-asserted-by":"publisher","DOI":"10.1007\/BF02992869"},{"key":"S0963548322000153_ref24","doi-asserted-by":"publisher","DOI":"10.1137\/15M1032910"},{"key":"S0963548322000153_ref11","doi-asserted-by":"publisher","DOI":"10.1007\/BF01895727"},{"key":"S0963548322000153_ref19","doi-asserted-by":"publisher","DOI":"10.1002\/9781118032718"},{"key":"S0963548322000153_ref26","first-page":"30","article-title":"Hamilton","volume":"25","author":"McDowell","year":"2018","journal-title":"Electron. J. Combin."},{"key":"S0963548322000153_ref2","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.22691"},{"key":"S0963548322000153_ref17","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20981"},{"key":"S0963548322000153_ref21","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20886"},{"key":"S0963548322000153_ref1","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s2-48.1.39"},{"key":"S0963548322000153_ref29","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(92)90141-2"},{"key":"S0963548322000153_ref14","first-page":"17","article-title":"On the evolution of random graphs","volume":"5","author":"Erd\u0151s","year":"1960","journal-title":"Magyar Tud. Akad. Mat. Kutat\u00f3 Int. K\u00f6zl."},{"key":"S0963548322000153_ref23","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548316000079"},{"key":"S0963548322000153_ref28","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2020.103118"},{"key":"S0963548322000153_ref7","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10070"},{"key":"S0963548322000153_ref8","doi-asserted-by":"publisher","DOI":"10.1112\/mtk.12005"},{"key":"S0963548322000153_ref27","doi-asserted-by":"publisher","DOI":"10.1137\/19M125412X"},{"key":"S0963548322000153_ref6","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10112"},{"key":"S0963548322000153_ref3","doi-asserted-by":"publisher","DOI":"10.37236\/5185"},{"key":"S0963548322000153_ref15","doi-asserted-by":"publisher","DOI":"10.1090\/tran\/7727"},{"key":"S0963548322000153_ref16","unstructured":"[16] Hajnal, A. and Szemer\u00e9di, E. (1970) Proof of a conjecture of P. Erd\u0151s. In Combinatorial theory and its applications, II (Proc. Colloq., Balatonf\u00fcred, pp.601\u2013623 ."},{"key":"S0963548322000153_ref10","first-page":"06136","article-title":"Cycle factors in randomly perturbed graphs","volume":"2103","author":"B\u00f6ttcher","year":"2021","journal-title":"arXiv"},{"key":"S0963548322000153_ref30","first-page":"pp.399","volume-title":"Colloq. Internat. CNRS 1976),","volume":"260","author":"Szemer\u00e9di","year":"1978"},{"key":"S0963548322000153_ref4","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548318000366"},{"key":"S0963548322000153_ref22","first-page":"pp.295","volume-title":"Combinatorics, Paul Erd\u0151s is eighty","author":"Koml\u00f3s","year":"1996"},{"key":"S0963548322000153_ref20","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20224"},{"key":"S0963548322000153_ref13","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20870"},{"key":"S0963548322000153_ref25","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20097"},{"key":"S0963548322000153_ref18","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.22365"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548322000153","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,20]],"date-time":"2022-12-20T05:08:17Z","timestamp":1671512897000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548322000153\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,7,5]]},"references-count":30,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,1]]}},"alternative-id":["S0963548322000153"],"URL":"https:\/\/doi.org\/10.1017\/s0963548322000153","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,7,5]]},"assertion":[{"value":"\u00a9 The Author(s), 2022. Published by Cambridge University Press","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}},{"value":"This is an Open Access article, distributed under the terms of the Creative Commons Attribution licence (https:\/\/creativecommons.org\/licenses\/by\/4.0\/), which permits unrestricted re-use, distribution, and reproduction in any medium, provided the original work is properly cited.","name":"license","label":"License","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}