{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,25]],"date-time":"2025-02-25T05:28:01Z","timestamp":1740461281936,"version":"3.37.3"},"reference-count":32,"publisher":"Cambridge University Press (CUP)","issue":"2","license":[{"start":{"date-parts":[[2024,12,3]],"date-time":"2024-12-03T00:00:00Z","timestamp":1733184000000},"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":[[2025,3]]},"abstract":"Abstract<\/jats:title>A graph \n$G$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> is \n$q$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>-Ramsey<\/jats:italic> for another graph \n$H$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> if in any \n$q$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>-edge-colouring of \n$G$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> there is a monochromatic copy of \n$H$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, and the classic Ramsey problem asks for the minimum number of vertices in such a graph. This was broadened in the seminal work of Burr, Erd\u0151s, and Lov\u00e1sz to the investigation of other extremal parameters of Ramsey graphs, including the minimum degree.<\/jats:p>It is not hard to see that if \n$G$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> is minimally \n$q$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>-Ramsey for \n$H$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> we must have \n$\\delta (G) \\ge q(\\delta (H) - 1) + 1$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, and we say that a graph \n$H$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> is \n$q$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>-Ramsey simple<\/jats:italic> if this bound can be attained. Grinshpun showed that this is typical of rather sparse graphs, proving that the random graph \n$G(n,p)$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> is almost surely \n$2$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>-Ramsey simple when \n$\\frac{\\log n}{n} \\ll p \\ll n^{-2\/3}$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>. In this paper, we explore this question further, asking for which pairs \n$p = p(n)$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> and \n$q = q(n,p)$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> we can expect \n$G(n,p)$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> to be \n$q$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>-Ramsey simple.<\/jats:p>We first extend Grinshpun\u2019s result by showing that \n$G(n,p)$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> is not just \n$2$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>-Ramsey simple, but is in fact \n$q$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>-Ramsey simple for any \n$q = q(n)$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, provided \n$p \\ll n^{-1}$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> or \n$\\frac{\\log n}{n} \\ll p \\ll n^{-2\/3}$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>. Next, when \n$p \\gg \\left ( \\frac{\\log n}{n} \\right )^{1\/2}$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, we find that \n$G(n,p)$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> is not \n$q$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>-Ramsey simple for any \n$q \\ge 2$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>. Finally, we uncover some interesting behaviour for intermediate edge probabilities. When \n$n^{-2\/3} \\ll p \\ll n^{-1\/2}$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, we find that there is some finite threshold \n$\\tilde{q} = \\tilde{q}(H)$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, depending on the structure of the instance \n$H \\sim G(n,p)$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> of the random graph, such that \n$H$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> is \n$q$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>-Ramsey simple if and only if \n$q \\le \\tilde{q}$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>. Aside from a couple of logarithmic factors, this resolves the qualitative nature of the Ramsey simplicity of the random graph over the full spectrum of edge probabilities.<\/jats:p>","DOI":"10.1017\/s0963548324000385","type":"journal-article","created":{"date-parts":[[2024,12,3]],"date-time":"2024-12-03T09:09:51Z","timestamp":1733216991000},"page":"298-320","update-policy":"https:\/\/doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":0,"title":["Ramsey simplicity of random graphs"],"prefix":"10.1017","volume":"34","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0276-8588","authenticated-orcid":false,"given":"Simona","family":"Boyadzhiyska","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5940-6556","authenticated-orcid":false,"given":"Dennis","family":"Clemens","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0004-4487-7741","authenticated-orcid":false,"given":"Shagnik","family":"Das","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2257-4139","authenticated-orcid":false,"given":"Pranshu","family":"Gupta","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2024,12,3]]},"reference":[{"key":"S0963548324000385_ref10","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.20199"},{"key":"S0963548324000385_ref4","unstructured":"[4] Campos, M. , Griffiths, S., Morris, R. and Sahasrabudhe, J. (2023) An exponential improvement for diagonal Ramsey, arXiv preprint arXiv: 2303.09521."},{"key":"S0963548324000385_ref12","unstructured":"[12] Bishnoi, A. and Lesgourgues, T. (2022) A new upper bound on the minimum degree of minimal Ramsey graphs. arXiv preprint arXiv: 2209.05147."},{"key":"S0963548324000385_ref25","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20953"},{"key":"S0963548324000385_ref8","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(75)90071-0"},{"key":"S0963548324000385_ref16","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.22064"},{"key":"S0963548324000385_ref14","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2014.06.003"},{"key":"S0963548324000385_ref27","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(85)90057-3"},{"key":"S0963548324000385_ref13","doi-asserted-by":"publisher","DOI":"10.1137\/21M1393273"},{"key":"S0963548324000385_ref1","doi-asserted-by":"publisher","DOI":"10.1112\/plms\/s2-30.1.264"},{"key":"S0963548324000385_ref20","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.20445"},{"key":"S0963548324000385_ref26","doi-asserted-by":"publisher","DOI":"10.1137\/050647116"},{"volume-title":"Introduction to random graphs","year":"2016","author":"Frieze","key":"S0963548324000385_ref29"},{"key":"S0963548324000385_ref7","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2009.170.941"},{"key":"S0963548324000385_ref21","first-page":"317","article-title":"Lower bounds on probability thresholds for Ramsey properties","volume":"1","author":"R\u00f6dl","year":"1993","journal-title":"Combinatorics, Paul Erd\u0151s is eighty"},{"key":"S0963548324000385_ref17","unstructured":"[17] Grinshpun, A. V. (2015) Some problems in graph Ramsey theory (Ph.D. thesis) Massachusetts Institute of Technology."},{"key":"S0963548324000385_ref2","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9904-1947-08785-1"},{"key":"S0963548324000385_ref30","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511814068"},{"key":"S0963548324000385_ref31","doi-asserted-by":"publisher","DOI":"10.1112\/plms\/83.3.532"},{"key":"S0963548324000385_ref6","doi-asserted-by":"publisher","DOI":"10.1215\/00127094-2022-0048"},{"key":"S0963548324000385_ref19","doi-asserted-by":"publisher","DOI":"10.1137\/17M1116696"},{"key":"S0963548324000385_ref18","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-019-3921-7"},{"key":"S0963548324000385_ref11","doi-asserted-by":"publisher","DOI":"10.1112\/blms.12658"},{"key":"S0963548324000385_ref5","unstructured":"[5] Gupta, P. , Ndiaye, N. , Norin, S. and Wei, L. (2024) Optimizing the CGMS upper bound on Ramsey numbers, arXiv preprint arXiv: 2407.19026."},{"key":"S0963548324000385_ref3","first-page":"463","article-title":"A combinatorial problem in geometry","volume":"2","author":"Erd\u0151s","year":"1935","journal-title":"Compos. Math."},{"key":"S0963548324000385_ref9","first-page":"167","article-title":"On graphs of Ramsey type","volume":"1","author":"Burr","year":"1976","journal-title":"Ars Combin."},{"key":"S0963548324000385_ref15","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2016.03.006"},{"key":"S0963548324000385_ref32","doi-asserted-by":"publisher","DOI":"10.37236\/5730"},{"key":"S0963548324000385_ref24","doi-asserted-by":"publisher","DOI":"10.1112\/blms\/bds097"},{"key":"S0963548324000385_ref23","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2009.03.004"},{"key":"S0963548324000385_ref28","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-12788-9_6"},{"key":"S0963548324000385_ref22","doi-asserted-by":"publisher","DOI":"10.1090\/S0894-0347-1995-1276825-6"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548324000385","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,24]],"date-time":"2025-02-24T12:38:44Z","timestamp":1740400724000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548324000385\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,12,3]]},"references-count":32,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,3]]}},"alternative-id":["S0963548324000385"],"URL":"https:\/\/doi.org\/10.1017\/s0963548324000385","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"type":"print","value":"0963-5483"},{"type":"electronic","value":"1469-2163"}],"subject":[],"published":{"date-parts":[[2024,12,3]]},"assertion":[{"value":"\u00a9 The Author(s), 2024. 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"}]}}