{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,13]],"date-time":"2026-01-13T09:25:27Z","timestamp":1768296327088,"version":"3.49.0"},"reference-count":44,"publisher":"Cambridge University Press (CUP)","issue":"6","license":[{"start":{"date-parts":[[2020,6,30]],"date-time":"2020-06-30T00:00:00Z","timestamp":1593475200000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2020,11]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Given graphs <jats:italic>H<\/jats:italic><jats:sub>1<\/jats:sub>, <jats:italic>H<\/jats:italic><jats:sub>2<\/jats:sub>, a graph <jats:italic>G<\/jats:italic> is (<jats:italic>H<\/jats:italic><jats:sub>1<\/jats:sub>, <jats:italic>H<\/jats:italic><jats:sub>2<\/jats:sub>) -Ramsey if, for every colouring of the edges of <jats:italic>G<\/jats:italic> with red and blue, there is a red copy of <jats:italic>H<\/jats:italic><jats:sub>1<\/jats:sub> or a blue copy of <jats:italic>H<\/jats:italic><jats:sub>2<\/jats:sub>. In this paper we investigate Ramsey questions in the setting of <jats:italic>randomly perturbed graphs<\/jats:italic>. This is a random graph model introduced by Bohman, Frieze and Martin [8] in which one starts with a dense graph and then adds a given number of random edges to it. The study of Ramsey properties of randomly perturbed graphs was initiated by Krivelevich, Sudakov and Tetali [30] in 2006; they determined how many random edges must be added to a dense graph to ensure the resulting graph is with high probability (<jats:italic>K<\/jats:italic><jats:sub>3<\/jats:sub>, <jats:italic>K<\/jats:italic><jats:sub><jats:italic>t<\/jats:italic><\/jats:sub>) -Ramsey (for <jats:italic>t<\/jats:italic> \u227d 3). They also raised the question of generalizing this result to pairs of graphs other than (<jats:italic>K<\/jats:italic><jats:sub>3<\/jats:sub>, <jats:italic>K<\/jats:italic><jats:sub><jats:italic>t<\/jats:italic><\/jats:sub>). We make significant progress on this question, giving a precise solution in the case when <jats:italic>H<\/jats:italic><jats:sub>1<\/jats:sub> = <jats:italic>K<\/jats:italic><jats:sub><jats:italic>s<\/jats:italic><\/jats:sub> and <jats:italic>H<\/jats:italic><jats:sub>2<\/jats:sub> = <jats:italic>K<\/jats:italic><jats:sub><jats:italic>t<\/jats:italic><\/jats:sub> where <jats:italic>s<\/jats:italic>, <jats:italic>t<\/jats:italic> \u227d 5. Although we again show that one requires polynomially fewer edges than in the purely random graph, our result shows that the problem in this case is quite different to the (<jats:italic>K<\/jats:italic><jats:sub>3<\/jats:sub>, <jats:italic>K<\/jats:italic><jats:sub><jats:italic>t<\/jats:italic><\/jats:sub>) -Ramsey question. Moreover, we give bounds for the corresponding (<jats:italic>K<\/jats:italic><jats:sub>4<\/jats:sub>, <jats:italic>K<\/jats:italic><jats:sub><jats:italic>t<\/jats:italic><\/jats:sub>) -Ramsey question; together with a construction of Powierski [37] this resolves the (<jats:italic>K<\/jats:italic><jats:sub>4<\/jats:sub>, <jats:italic>K<\/jats:italic><jats:sub>4<\/jats:sub>) -Ramsey problem.<\/jats:p><jats:p>We also give a precise solution to the analogous question in the case when both <jats:italic>H<\/jats:italic><jats:sub>1<\/jats:sub> = <jats:italic>C<\/jats:italic><jats:sub><jats:italic>s<\/jats:italic><\/jats:sub> and <jats:italic>H<\/jats:italic><jats:sub>2<\/jats:sub> = <jats:italic>C<\/jats:italic><jats:sub><jats:italic>t<\/jats:italic><\/jats:sub> are cycles. Additionally we consider the corresponding multicolour problem. Our final result gives another generalization of the Krivelevich, Sudakov and Tetali [30] result. Specifically, we determine how many random edges must be added to a dense graph to ensure the resulting graph is with high probability (<jats:italic>C<\/jats:italic><jats:sub><jats:italic>s<\/jats:italic><\/jats:sub>, <jats:italic>K<\/jats:italic><jats:sub><jats:italic>t<\/jats:italic><\/jats:sub>) -Ramsey (for odd <jats:italic>s<\/jats:italic> \u227d 5 and <jats:italic>t<\/jats:italic> \u227d 4).<\/jats:p><jats:p>To prove our results we combine a mixture of approaches, employing the container method, the regularity method as well as dependent random choice, and apply robust extensions of recent asymmetric random Ramsey results.<\/jats:p>","DOI":"10.1017\/s0963548320000231","type":"journal-article","created":{"date-parts":[[2020,6,30]],"date-time":"2020-06-30T09:09:47Z","timestamp":1593508187000},"page":"830-867","update-policy":"https:\/\/doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":13,"title":["Ramsey properties of randomly perturbed graphs: cliques and cycles"],"prefix":"10.1017","volume":"29","author":[{"given":"Shagnik","family":"Das","sequence":"first","affiliation":[]},{"given":"Andrew","family":"Treglown","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2020,6,30]]},"reference":[{"key":"S0963548320000231_ref39","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240050202"},{"key":"S0963548320000231_ref27","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1098-2418(199610)9:3<335::AID-RSA5>3.0.CO;2-Y"},{"key":"S0963548320000231_ref41","doi-asserted-by":"publisher","DOI":"10.1007\/s00222-014-0562-8"},{"key":"S0963548320000231_ref7","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10112"},{"key":"S0963548320000231_ref20","doi-asserted-by":"publisher","DOI":"10.1017\/fms.2017.22"},{"key":"S0963548320000231_ref10","doi-asserted-by":"publisher","DOI":"10.1112\/mtk.12005"},{"key":"S0963548320000231_ref11","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-0118(199705)25:1<3::AID-JGT1>3.0.CO;2-R"},{"key":"S0963548320000231_ref13","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2016.184.2.2"},{"key":"S0963548320000231_ref28","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548316000079"},{"key":"S0963548320000231_ref1","doi-asserted-by":"publisher","DOI":"10.1137\/18M1227007"},{"key":"S0963548320000231_ref38","unstructured":"[38] R\u00f6dl, V. and Ruci\u0144ski, A. (1993) Lower bounds on probability thresholds for Ramsey properties. In Combinatorics: Paul Erd\u0151s is Eighty, Vol. 1 ( Mikl\u00f3s, D. , S\u00f3s, V. T. and Sz\u0151nyi, T. , eds), pp. 317\u2013346, J\u00e1nos Bolyai Mathematical Society."},{"key":"S0963548320000231_ref16","first-page":"515","article-title":"On partition theorems for finite graphs","volume":"10","author":"Erd\u0151s","year":"1973","journal-title":"Colloq. Math. Soc. J\u00e1nos Bolyai."},{"key":"S0963548320000231_ref2","volume-title":"The Probabilistic Method","author":"Alon","year":"2015"},{"key":"S0963548320000231_ref3","doi-asserted-by":"publisher","DOI":"10.1090\/S0894-0347-2014-00816-X"},{"key":"S0963548320000231_ref4","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548318000366"},{"key":"S0963548320000231_ref34","unstructured":"[34] Mousset, F. , Nenadov, R. and Samotij, W. (2018) Towards the Kohayakawa\u2013Kreuter conjecture on asymmetric Ramsey properties. Comb. Probab. Comput. arXiv:1808.05070"},{"key":"S0963548320000231_ref44","first-page":"436","article-title":"On an extremal problem in graph theory (in Hungarian)","volume":"48","author":"Tur\u00e1n","year":"1941","journal-title":"Math. Fiz. Lapok"},{"key":"S0963548320000231_ref36","unstructured":"[36] Nenadov, R. and Truji\u0107, M. (2018) Sprinkling a few random edges doubles the power. arXiv:1811.09209"},{"key":"S0963548320000231_ref35","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548314000832"},{"key":"S0963548320000231_ref15","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20870"},{"key":"S0963548320000231_ref14","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2016.12.005"},{"key":"S0963548320000231_ref30","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20097"},{"key":"S0963548320000231_ref9","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20850"},{"key":"S0963548320000231_ref31","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(92)90006-J"},{"key":"S0963548320000231_ref40","doi-asserted-by":"publisher","DOI":"10.2307\/2152833"},{"key":"S0963548320000231_ref32","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20239"},{"key":"S0963548320000231_ref29","doi-asserted-by":"publisher","DOI":"10.1137\/15M1032910"},{"key":"S0963548320000231_ref33","doi-asserted-by":"publisher","DOI":"10.37236\/7671"},{"key":"S0963548320000231_ref43","unstructured":"[43] Szemer\u00e9di, E. (1976) Regular partitions of graphs. In Probl\u00e8mes Combinatoires et Th\u00e9orie des Graphes, Vol. 260 of Colloques Internationaux CNRS, pp. 399\u2013401."},{"key":"S0963548320000231_ref26","unstructured":"[26] Koml\u00f3s, J. and Simonovits, M. (1996) Szemer\u00e9di\u2019s Regularity Lemma and its applications in graph theory. In Combinatorics: Paul Erd\u00f6s is Eighty, Vol. 2 ( Mikl\u00f3s, D. , S\u00f3s, V. T. and Sz\u0151nyi, T. eds.), pp. 295\u2013352, J\u00e1nos Bolyai Mathematical Society."},{"key":"S0963548320000231_ref12","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2009.170.941"},{"key":"S0963548320000231_ref8","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10070"},{"key":"S0963548320000231_ref23","doi-asserted-by":"publisher","DOI":"10.1002\/9781118032718"},{"key":"S0963548320000231_ref25","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1098-2418(199710)11:3<245::AID-RSA3>3.0.CO;2-0"},{"key":"S0963548320000231_ref18","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20344"},{"key":"S0963548320000231_ref19","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20352"},{"key":"S0963548320000231_ref17","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9904-1946-08715-7"},{"key":"S0963548320000231_ref24","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20886"},{"key":"S0963548320000231_ref5","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20885"},{"key":"S0963548320000231_ref6","unstructured":"[6] Bennett, P. , Dudek, A. and Frieze, A. (2017) Adding random edges to create the square of a Hamilton cycle. arXiv:1710.02716"},{"key":"S0963548320000231_ref37","unstructured":"[37] Powierski, E. (2019) Ramsey properties of randomly perturbed dense graphs. arXiv:1902.02197"},{"key":"S0963548320000231_ref21","unstructured":"[21] Han, J. and Zhao, Y. Hamiltonicity in randomly perturbed hypergraphs. J. Combin. Theory Ser. B, to appear."},{"key":"S0963548320000231_ref22","doi-asserted-by":"publisher","DOI":"10.1137\/18M119642X"},{"key":"S0963548320000231_ref42","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(75)90071-0"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548320000231","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,11]],"date-time":"2020-11-11T12:44:24Z","timestamp":1605098664000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548320000231\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,30]]},"references-count":44,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2020,11]]}},"alternative-id":["S0963548320000231"],"URL":"https:\/\/doi.org\/10.1017\/s0963548320000231","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,6,30]]},"assertion":[{"value":"\u00a9 The Author(s), 2020. Published by Cambridge University Press","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}}]}}