{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,27]],"date-time":"2026-01-27T12:39:25Z","timestamp":1769517565906,"version":"3.49.0"},"reference-count":28,"publisher":"MathDoc\/Centre Mersenne","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"abstract":"\n For a given\n \n \n \u03b4<\/mml:mi>\n \u2208<\/mml:mo>\n (<\/mml:mo>\n 0<\/mml:mn>\n ,<\/mml:mo>\n 1<\/mml:mn>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n , the randomly perturbed graph model is defined as the union of any\n \n n<\/mml:mi>\n <\/mml:math>\n -vertex graph\n \n \n G<\/mml:mi>\n 0<\/mml:mn>\n <\/mml:msub>\n <\/mml:math>\n with minimum degree\n \n \n \u03b4<\/mml:mi>\n n<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n and the binomial random graph\n \n \n G<\/mml:mi>\n (<\/mml:mo>\n n<\/mml:mi>\n ,<\/mml:mo>\n p<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n on the same vertex set. Moreover, we say that a graph is uniformly coloured with colours in\n \n \ud835\udc9e<\/mml:mi>\n <\/mml:math>\n if each edge is coloured independently and uniformly at random with a colour from\n \n \ud835\udc9e<\/mml:mi>\n <\/mml:math>\n .\n <\/jats:p>\n \n Based on a coupling idea of McDiarmid, we provide a general tool to tackle problems concerning finding a rainbow copy of a graph\n \n \n H<\/mml:mi>\n =<\/mml:mo>\n H<\/mml:mi>\n (<\/mml:mo>\n n<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n in a uniformly coloured perturbed\n \n n<\/mml:mi>\n <\/mml:math>\n -vertex graph with colours in\n \n \n [<\/mml:mo>\n (<\/mml:mo>\n 1<\/mml:mn>\n +<\/mml:mo>\n o<\/mml:mi>\n (<\/mml:mo>\n 1<\/mml:mn>\n )<\/mml:mo>\n )<\/mml:mo>\n e<\/mml:mi>\n (<\/mml:mo>\n H<\/mml:mi>\n )<\/mml:mo>\n ]<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n . For example, our machinery easily allows to recover a result of Aigner-Horev and Hefetz concerning rainbow Hamilton cycles, and to improve a result of Aigner-Horev, Hefetz and Lahiri concerning rainbow bounded-degree spanning trees.\n <\/jats:p>\n \n Furthermore, using different methods, we prove that for any\n \n \n \u03b4<\/mml:mi>\n \u2208<\/mml:mo>\n (<\/mml:mo>\n 0<\/mml:mn>\n ,<\/mml:mo>\n 1<\/mml:mn>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n and integer\n \n \n d<\/mml:mi>\n \u2265<\/mml:mo>\n 2<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math>\n , there exists\n \n \n C<\/mml:mi>\n =<\/mml:mo>\n C<\/mml:mi>\n (<\/mml:mo>\n \u03b4<\/mml:mi>\n ,<\/mml:mo>\n d<\/mml:mi>\n )<\/mml:mo>\n ><\/mml:mo>\n 0<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math>\n such that the following holds. Let\n \n T<\/mml:mi>\n <\/mml:math>\n be a tree on\n \n n<\/mml:mi>\n <\/mml:math>\n vertices with maximum degree at most\n \n d<\/mml:mi>\n <\/mml:math>\n and\n \n \n G<\/mml:mi>\n 0<\/mml:mn>\n <\/mml:msub>\n <\/mml:math>\n be an\n \n n<\/mml:mi>\n <\/mml:math>\n -vertex graph with\n \n \n \u03b4<\/mml:mi>\n (<\/mml:mo>\n \n G<\/mml:mi>\n 0<\/mml:mn>\n <\/mml:msub>\n )<\/mml:mo>\n \u2265<\/mml:mo>\n \u03b4<\/mml:mi>\n n<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n . Then a uniformly coloured\n \n \n \n G<\/mml:mi>\n 0<\/mml:mn>\n <\/mml:msub>\n \u222a<\/mml:mo>\n G<\/mml:mi>\n \n (<\/mml:mo>\n n<\/mml:mi>\n ,<\/mml:mo>\n C<\/mml:mi>\n \/<\/mml:mo>\n n<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math>\n with colours in\n \n \n [<\/mml:mo>\n n<\/mml:mi>\n -<\/mml:mo>\n 1<\/mml:mn>\n ]<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n contains a rainbow copy of\n \n T<\/mml:mi>\n <\/mml:math>\n with high probability. This is optimal both in terms of colours and edge probability (up to a constant factor).\n <\/jats:p>","DOI":"10.5802\/igt.12","type":"journal-article","created":{"date-parts":[[2025,11,13]],"date-time":"2025-11-13T15:54:02Z","timestamp":1763049242000},"page":"245-273","source":"Crossref","is-referenced-by-count":0,"title":["Rainbow subgraphs of uniformly coloured randomly perturbed graphs"],"prefix":"10.5802","volume":"2","author":[{"given":"Kyriakos","family":"Katsamaktsis","sequence":"first","affiliation":[{"name":"Department of Mathematics, University College London, London, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shoham","family":"Letzter","sequence":"additional","affiliation":[{"name":"Department of Mathematics, University College London, London, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Amedeo","family":"Sgueglia","sequence":"additional","affiliation":[{"name":"Fakult\u00e4t f\u00fcr Informatik und Mathematik, Universit\u00e4t Passau, Passau, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"3842","published-online":{"date-parts":[[2025,11,13]]},"reference":[{"issue":"3","key":"key2025121216553429627_1","doi-asserted-by":"publisher","first-page":"1569","DOI":"10.1137\/20M1332992","article-title":"Rainbow Hamilton cycles in randomly colored randomly perturbed dense graphs","volume":"35","author":"Aigner-Horev, E.","year":"2021","unstructured":"[1] Aigner-Horev, E.; Hefetz, D. Rainbow Hamilton cycles in randomly colored randomly perturbed dense graphs, SIAM J. Discrete Math., Volume 35 (2021) no. 3, pp. 1569-1577","journal-title":"SIAM J. Discrete Math."},{"issue":"2","key":"key2025121216553429627_2","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1002\/rsa.21103","article-title":"Rainbow trees in uniformly edge-colored graphs","volume":"62","author":"Aigner-Horev, E.","year":"2023","unstructured":"[2] Aigner-Horev, E.; Hefetz, D.; Lahiri, A. Rainbow trees in uniformly edge-colored graphs, Random Struct. Algorithms, Volume 62 (2023) no. 2, pp. 287-303","journal-title":"Random Struct. Algorithms"},{"issue":"6","key":"key2025121216553429627_3","doi-asserted-by":"publisher","first-page":"629","DOI":"10.1007\/s00493-007-2182-z","article-title":"Embedding nearly-spanning bounded degree trees","volume":"27","author":"Alon, N.","year":"2007","unstructured":"[3] Alon, N.; Krivelevich, M.; Sudakov, B. Embedding nearly-spanning bounded degree trees, Combinatorica, Volume 27 (2007) no. 6, pp. 629-644","journal-title":"Combinatorica"},{"issue":"2","key":"key2025121216553429627_4","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1002\/jgt.22691","article-title":"High powers of Hamiltonian cycles in randomly augmented graphs","volume":"98","author":"Antoniuk, S.","year":"2021","unstructured":"[4] Antoniuk, S.; Dudek, A.; Reiher, C.; Ruci\u0144ski, A.; Schacht, M. High powers of Hamiltonian cycles in randomly augmented graphs, J. Graph Theory, Volume 98 (2021) no. 2, pp. 255-284","journal-title":"J. Graph Theory"},{"issue":"4","key":"key2025121216553429627_5","doi-asserted-by":"publisher","first-page":"811","DOI":"10.1002\/jgt.23001","article-title":"Powers of Hamiltonian cycles in randomly augmented Dirac graphs\u2014the complete collection","volume":"104","author":"Antoniuk, S.","year":"2023","unstructured":"[5] Antoniuk, S.; Dudek, A.; Ruci\u0144ski, A. Powers of Hamiltonian cycles in randomly augmented Dirac graphs\u2014the complete collection, J. Graph Theory, Volume 104 (2023) no. 4, pp. 811-835","journal-title":"J. Graph Theory"},{"issue":"3","key":"key2025121216553429627_6","doi-asserted-by":"publisher","first-page":"503","DOI":"10.1002\/rsa.20594","article-title":"Rainbow matchings and Hamilton cycles in random graphs","volume":"48","author":"Bal, D.","year":"2016","unstructured":"[6] Bal, D.; Frieze, A. Rainbow matchings and Hamilton cycles in random graphs, Random Struct. Algorithms, Volume 48 (2016) no. 3, pp. 503-523","journal-title":"Random Struct. Algorithms"},{"issue":"2","key":"key2025121216553429627_7","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1017\/S0963548318000366","article-title":"Tilings in randomly perturbed dense graphs","volume":"28","author":"Balogh, J.","year":"2019","unstructured":"[7] Balogh, J.; Treglown, A.; Wagner, A. Z. Tilings in randomly perturbed dense graphs, Comb. Probab. Comput., Volume 28 (2019) no. 2, pp. 159-176","journal-title":"Comb. Probab. Comput."},{"issue":"1","key":"key2025121216553429627_8","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1002\/rsa.10070","article-title":"How many random edges make a dense graph Hamiltonian?","volume":"22","author":"Bohman, T.","year":"2003","unstructured":"[8] Bohman, T.; Frieze, A.; Martin, R. How many random edges make a dense graph Hamiltonian?, Random Struct. Algorithms, Volume 22 (2003) no. 1, pp. 33-42","journal-title":"Random Struct. Algorithms"},{"issue":"4","key":"key2025121216553429627_9","doi-asserted-by":"publisher","first-page":"854","DOI":"10.1002\/rsa.20850","article-title":"Universality for bounded degree spanning trees in randomly perturbed graphs","volume":"55","author":"B\u00f6ttcher, J.","year":"2019","unstructured":"[9] B\u00f6ttcher, J.; Han, J.; Kohayakawa, Y.; Montgomery, R.; Parczyk, O.; Person, Y. Universality for bounded degree spanning trees in randomly perturbed graphs, Random Struct. Algorithms, Volume 55 (2019) no. 4, pp. 854-864","journal-title":"Random Struct. Algorithms"},{"issue":"2","key":"key2025121216553429627_10","doi-asserted-by":"publisher","first-page":"422","DOI":"10.1112\/mtk.12005","article-title":"Embedding spanning bounded graphs in randomly perturbed graphs","volume":"66","author":"B\u00f6ttcher, J.","year":"2020","unstructured":"[10] B\u00f6ttcher, J.; Montgomery, R.; Parczyk, O.; Person, Y. Embedding spanning bounded graphs in randomly perturbed graphs, Mathematika, Volume 66 (2020) no. 2, pp. 422-447","journal-title":"Mathematika"},{"issue":"1","key":"key2025121216553429627_11","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1017\/S0963548322000153","article-title":"Triangles in randomly perturbed graphs","volume":"32","author":"B\u00f6ttcher, J.","year":"2023","unstructured":"[11] B\u00f6ttcher, J.; Parczyk, O.; Sgueglia, A.; Skokan, J. Triangles in randomly perturbed graphs, Comb. Probab. Comput., Volume 32 (2023) no. 1, pp. 91-121","journal-title":"Comb. Probab. Comput."},{"issue":"2","key":"key2025121216553429627_12","doi-asserted-by":"publisher","first-page":"342","DOI":"10.1002\/rsa.21215","article-title":"The square of a Hamilton cycle in randomly perturbed graphs","volume":"65","author":"B\u00f6ttcher, J.","year":"2024","unstructured":"[12] B\u00f6ttcher, J.; Parczyk, O.; Sgueglia, A.; Skokan, J. The square of a Hamilton cycle in randomly perturbed graphs, Random Struct. Algorithms, Volume 65 (2024) no. 2, pp. 342-386","journal-title":"Random Struct. Algorithms"},{"issue":"1","key":"key2025121216553429627_13","doi-asserted-by":"publisher","first-page":"122","DOI":"10.1002\/rsa.20870","article-title":"Powers of Hamiltonian cycles in randomly augmented graphs","volume":"56","author":"Dudek, A.","year":"2020","unstructured":"[13] Dudek, A.; Reiher, C.; Ruci\u0144ski, A.; Schacht, M. Powers of Hamiltonian cycles in randomly augmented graphs, Random Struct. Algorithms, Volume 56 (2020) no. 1, pp. 122-141","journal-title":"Random Struct. Algorithms"},{"issue":"1","key":"key2025121216553429627_14","article-title":"Closing gaps in problems related to Hamilton cycles in random graphs and hypergraphs","volume":"22","author":"Ferber, A.","year":"2015","unstructured":"[14] Ferber, A. Closing gaps in problems related to Hamilton cycles in random graphs and hypergraphs, Electron. J. Comb., Volume 22 (2015) no. 1, 1.61, 7 pages","journal-title":"Electron. J. Comb."},{"key":"key2025121216553429627_15","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1007\/978-3-319-24298-9_7","article-title":"Rainbow Hamilton cycles in random graphs and hypergraphs","volume":"159","author":"Ferber, A.","year":"2016","unstructured":"[15] Ferber, A.; Krivelevich, M. Rainbow Hamilton cycles in random graphs and hypergraphs, Recent trends in combinatorics (The IMA Volumes in Mathematics and its Applications), Volume 159, Springer, 2016, pp. 167-189","journal-title":"Recent trends in combinatorics"},{"issue":"3","key":"key2025121216553429627_16","doi-asserted-by":"publisher","first-page":"328","DOI":"10.1002\/rsa.20475","article-title":"Rainbow Hamilton cycles in random graphs","volume":"44","author":"Frieze, A.","year":"2014","unstructured":"[16] Frieze, A.; Loh, P.-S. Rainbow Hamilton cycles in random graphs, Random Struct. Algorithms, Volume 44 (2014) no. 3, pp. 328-354","journal-title":"Random Struct. Algorithms"},{"key":"key2025121216553429627_17","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1016\/j.jctb.2022.04.003","article-title":"Almost all optimally coloured complete graphs contain a rainbow Hamilton path","volume":"156","author":"Gould, S.","year":"2022","unstructured":"[17] Gould, S.; Kelly, T.; K\u00fchn, D.; Osthus, D. Almost all optimally coloured complete graphs contain a rainbow Hamilton path, J. Comb. Theory, Ser. B, Volume 156 (2022), pp. 57-100","journal-title":"J. Comb. Theory, Ser. B"},{"issue":"3","key":"key2025121216553429627_18","doi-asserted-by":"publisher","first-page":"480","DOI":"10.1002\/rsa.20981","article-title":"Tilings in randomly perturbed graphs: bridging the gap between Hajnal-Szemer\u00e9di and Johansson-Kahn-Vu","volume":"58","author":"Han, J.","year":"2021","unstructured":"[18] Han, J.; Morris, P.; Treglown, A. Tilings in randomly perturbed graphs: bridging the gap between Hajnal-Szemer\u00e9di and Johansson-Kahn-Vu, Random Struct. Algorithms, Volume 58 (2021) no. 3, pp. 480-516","journal-title":"Random Struct. Algorithms"},{"key":"key2025121216553429627_19","author":"Janson, S.","year":"2011","unstructured":"[19] Janson, S.; Ruci\u0144ski, A.; \u0141uczak, T. Random Graphs, John Wiley & Sons, 2011","journal-title":"Random Graphs"},{"issue":"1","key":"key2025121216553429627_20","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1002\/rsa.20886","article-title":"Spanning trees in randomly perturbed graphs","volume":"56","author":"Joos, F.","year":"2020","unstructured":"[20] Joos, F.; Kim, J. Spanning trees in randomly perturbed graphs, Random Struct. Algorithms, Volume 56 (2020) no. 1, pp. 169-219","journal-title":"Random Struct. Algorithms"},{"key":"key2025121216553429627_21","author":"Katsamaktsis, K.","year":"2023","unstructured":"[21] Katsamaktsis, K.; Letzter, S. Rainbow Hamiltonicity in uniformly coloured perturbed graphs (2023)","journal-title":"Rainbow Hamiltonicity in uniformly coloured perturbed graphs"},{"issue":"5","key":"key2025121216553429627_22","doi-asserted-by":"publisher","first-page":"624","DOI":"10.1017\/S0963548324000130","article-title":"Rainbow Hamiltonicity in uniformly coloured perturbed digraphs","volume":"33","author":"Katsamaktsis, K.","year":"2024","unstructured":"[22] Katsamaktsis, K.; Letzter, S.; Sgueglia, A. Rainbow Hamiltonicity in uniformly coloured perturbed digraphs, Comb. Probab. Comput., Volume 33 (2024) no. 5, pp. 624-642","journal-title":"Comb. Probab. Comput."},{"issue":"4","key":"key2025121216553429627_23","doi-asserted-by":"publisher","first-page":"1495","DOI":"10.1137\/100805753","article-title":"Embedding spanning trees in random graphs","volume":"24","author":"Krivelevich, M.","year":"2010","unstructured":"[23] Krivelevich, M. Embedding spanning trees in random graphs, SIAM J. Discrete Math., Volume 24 (2010) no. 4, pp. 1495-1500","journal-title":"SIAM J. Discrete Math."},{"issue":"1","key":"key2025121216553429627_24","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1137\/15M1032910","article-title":"Bounded-degree spanning trees in randomly perturbed graphs","volume":"31","author":"Krivelevich, M.","year":"2017","unstructured":"[24] Krivelevich, M.; Kwan, M.; Sudakov, B. Bounded-degree spanning trees in randomly perturbed graphs, SIAM J. Discrete Math., Volume 31 (2017) no. 1, pp. 155-171","journal-title":"SIAM J. Discrete Math."},{"key":"key2025121216553429627_25","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1007\/BFb0120903","article-title":"Clutter percolation and random graphs","volume":"13","author":"McDiarmid, C.","year":"1980","unstructured":"[25] McDiarmid, C. Clutter percolation and random graphs, Math. Program. Study, Volume 13 (1980), pp. 17-25","journal-title":"Math. Program. Study"},{"key":"key2025121216553429627_26","author":"Montgomery, R.","year":"2014","unstructured":"[26] Montgomery, R. Embedding bounded degree spanning trees in random graphs (2014)","journal-title":"Embedding bounded degree spanning trees in random graphs"},{"key":"key2025121216553429627_27","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2019.106793","article-title":"Spanning trees in random graphs","volume":"356","author":"Montgomery, R.","year":"2019","unstructured":"[27] Montgomery, R. Spanning trees in random graphs, Adv. Math., Volume 356 (2019), 106793, 92 pages","journal-title":"Adv. Math."},{"issue":"2","key":"key2025121216553429627_28","doi-asserted-by":"publisher","first-page":"988","DOI":"10.1137\/19M125412X","article-title":"Sprinkling a few random edges doubles the power","volume":"35","author":"Nenadov, R.","year":"2021","unstructured":"[28] Nenadov, R.; Truji\u0107, M. Sprinkling a few random edges doubles the power, SIAM J. Discrete Math., Volume 35 (2021) no. 2, pp. 988-1004","journal-title":"SIAM J. Discrete Math."}],"container-title":["Innovations in Graph Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/igt.centre-mersenne.org\/item\/10.5802\/igt.12.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,12,12]],"date-time":"2025-12-12T15:55:40Z","timestamp":1765554940000},"score":1,"resource":{"primary":{"URL":"https:\/\/igt.centre-mersenne.org\/articles\/10.5802\/igt.12\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,11,13]]},"references-count":28,"alternative-id":["10.5802\/igt.12"],"URL":"https:\/\/doi.org\/10.5802\/igt.12","relation":{},"ISSN":["3050-743X"],"issn-type":[{"value":"3050-743X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,11,13]]}}}