{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,1]],"date-time":"2026-03-01T12:54:06Z","timestamp":1772369646892,"version":"3.50.1"},"reference-count":23,"publisher":"Cambridge University Press (CUP)","issue":"3","license":[{"start":{"date-parts":[[2008,9,12]],"date-time":"2008-09-12T00:00:00Z","timestamp":1221177600000},"content-version":"unspecified","delay-in-days":4760,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[1995,9]]},"abstract":"<jats:p>For a graph <jats:italic>H<\/jats:italic> and an integer <jats:italic>r<\/jats:italic> \u2265 2, the <jats:italic>induced r-size-Ramsey number<\/jats:italic> of <jats:italic>H<\/jats:italic> is defined to be the smallest integer <jats:italic>m<\/jats:italic> for which there exists a graph <jats:italic>G<\/jats:italic> with <jats:italic>m<\/jats:italic> edges with the following property: however one colours the edges of <jats:italic>G<\/jats:italic> with <jats:italic>r<\/jats:italic> colours, there always exists a monochromatic induced subgraph <jats:italic>H<\/jats:italic>\u2032 of <jats:italic>G<\/jats:italic> that is isomorphic to <jats:italic>H<\/jats:italic>. This is a concept closely related to the classical <jats:italic>r<\/jats:italic>-size-Ramsey number of Erd\u0151s, Faudree, Rousseau and Schelp, and to the <jats:italic>r<\/jats:italic>-induced Ramsey number, a natural notion that appears in problems and conjectures due to, among others, Graham and R\u00f6dl, and Trotter. Here, we prove a result that implies that the induced <jats:italic>r<\/jats:italic>-size-Ramsey number of the cycle <jats:italic>C<jats:sup>\u2113<\/jats:sup><\/jats:italic> is at most <jats:italic>c<jats:sub>r<\/jats:sub><\/jats:italic>\u2113 for some constant <jats:italic>c<jats:sup>r<\/jats:sup><\/jats:italic> that depends only upon <jats:italic>r<\/jats:italic>. Thus we settle a conjecture of Graham and R\u00f6dl, which states that the above holds for the path <jats:italic>P<\/jats:italic><jats:sup>\u2113<\/jats:sup> of order \u2113 and also generalise in part a result of Bollob\u00e1s, Burr and Reimer that implies that the <jats:italic>r<\/jats:italic>-size Ramsey number of the cycle <jats:italic>C<\/jats:italic><jats:sup>\u2113<\/jats:sup> is linear in \u2113 Our method of proof is heavily based on techniques from the theory of random graphs and on a variant of the powerful regularity lemma of Szemer\u00e9di.<\/jats:p>","DOI":"10.1017\/s0963548300001619","type":"journal-article","created":{"date-parts":[[2008,9,12]],"date-time":"2008-09-12T11:15:38Z","timestamp":1221218138000},"page":"217-239","source":"Crossref","is-referenced-by-count":58,"title":["The Induced Size-Ramsey Number of Cycles"],"prefix":"10.1017","volume":"4","author":[{"given":"P. E.","family":"Haxell","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Y.","family":"Kohayakawa","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"T.","family":"\u0141uczak","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2008,9,12]]},"reference":[{"key":"S0963548300001619_ref010","doi-asserted-by":"publisher","DOI":"10.1007\/BF02018930"},{"key":"S0963548300001619_ref014","doi-asserted-by":"publisher","DOI":"10.1007\/BF02808204"},{"key":"S0963548300001619_ref003","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-72905-8_4"},{"key":"S0963548300001619_ref015","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1963.10500830"},{"key":"S0963548300001619_ref002","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190070115"},{"key":"S0963548300001619_ref021","unstructured":"[21] R\u00f6dl V. (1993) Personal communication."},{"key":"S0963548300001619_ref023","first-page":"436","article-title":"On an extremal problem in graph theory","volume":"48","author":"Tur\u00e1n","year":"1941","journal-title":"Mat. Fiz. Lapok"},{"key":"S0963548300001619_ref013","first-page":"111","volume-title":"Numbers in Ramsey theory. Surveys in Combinatorics, London Mathematical Society Lecture Note Series 123","author":"Graham","year":"1987"},{"key":"S0963548300001619_ref004","first-page":"401","article-title":"An upper bound for diagonal Ramsey numbers","volume":"18","author":"Beck","year":"1983","journal-title":"Studia Sci. Math."},{"key":"S0963548300001619_ref012","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(93)90521-T"},{"key":"S0963548300001619_ref009","first-page":"323","volume-title":"Infinite and Finite Sets, Colloq. Math. Soc. J. Bolyai","volume":"10","author":"Deuber","year":"1975"},{"key":"S0963548300001619_ref001","volume-title":"The Probabilistic Method","author":"Alon","year":"1992"},{"key":"S0963548300001619_ref005","volume-title":"Random Graphs","author":"Bollob\u00e1s","year":"1985"},{"key":"S0963548300001619_ref020","unstructured":"[20] R\u00f6dl V. (1973) The dimension of a graph and generalized Ramsey theorems. Thesis, Charles University, Praha."},{"key":"S0963548300001619_ref022","first-page":"399","volume-title":"Probl\u00e8mes en Combinatoire et Th\u00e9orie des Graphes, Proc. Colloque Inter. CNRS","author":"Szemer\u00e9di","year":"1978"},{"key":"S0963548300001619_ref008","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(83)90037-0"},{"key":"S0963548300001619_ref011","first-page":"585","volume-title":"Infinite and Finite Sets, Colloq. Math. Soc. J. Bolyai","volume":"10","author":"Erd\u0151s","year":"1975"},{"key":"S0963548300001619_ref006","unstructured":"[6] Bollob\u00e1s B. (1992) Personal communication."},{"key":"S0963548300001619_ref018","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(93)90230-Q"},{"key":"S0963548300001619_ref016","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240040106"},{"key":"S0963548300001619_ref017","unstructured":"[17] Kohayakawa Y. (1993) The regularity lemma of Szem\u00e9redi for sparse graphs. Manuscript."},{"key":"S0963548300001619_ref019","first-page":"148","volume-title":"On the method of bounded differences. Surveys in Combinatorics 1989, London Mathematical Society Lecture Notes Series 141","author":"McDiarmid","year":"1989"},{"key":"S0963548300001619_ref007","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1993.1012"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548300001619","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,13]],"date-time":"2019-05-13T21:04:42Z","timestamp":1557781482000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548300001619\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995,9]]},"references-count":23,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1995,9]]}},"alternative-id":["S0963548300001619"],"URL":"https:\/\/doi.org\/10.1017\/s0963548300001619","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[1995,9]]}}}