{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T09:15:38Z","timestamp":1725873338424},"reference-count":29,"publisher":"Cambridge University Press (CUP)","issue":"5","license":[{"start":{"date-parts":[[2021,4,12]],"date-time":"2021-04-12T00:00:00Z","timestamp":1618185600000},"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":[[2021,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Erd\u0151s asked if, for every pair of positive integers <jats:italic>g<\/jats:italic> and <jats:italic>k<\/jats:italic>, there exists a graph <jats:italic>H<\/jats:italic> having girth (<jats:italic>H<\/jats:italic>) = <jats:italic>k<\/jats:italic> and the property that every <jats:italic>r<\/jats:italic>-colouring of the edges of <jats:italic>H<\/jats:italic> yields a monochromatic cycle <jats:italic>C<\/jats:italic><jats:sub><jats:italic>k<\/jats:italic><\/jats:sub>. The existence of such graphs <jats:italic>H<\/jats:italic> was confirmed by the third author and Ruci\u0144ski.<\/jats:p><jats:p>We consider the related numerical problem of estimating the order of the smallest graph <jats:italic>H<\/jats:italic> with this property for given integers <jats:italic>r<\/jats:italic> and <jats:italic>k<\/jats:italic>. We show that there exists a graph <jats:italic>H<\/jats:italic> on <jats:italic>R<\/jats:italic><jats:sup>10<jats:italic>k<\/jats:italic><jats:sup>2<\/jats:sup><\/jats:sup>; <jats:italic>k<\/jats:italic><jats:sup>15<jats:italic>k<\/jats:italic><jats:sup>3<\/jats:sup><\/jats:sup> vertices (where <jats:italic>R<\/jats:italic> = <jats:italic>R<\/jats:italic>(<jats:italic>C<\/jats:italic><jats:sub><jats:italic>k<\/jats:italic><\/jats:sub>; <jats:italic>r<\/jats:italic>) is the <jats:italic>r<\/jats:italic>-colour Ramsey number for the cycle <jats:italic>C<\/jats:italic><jats:sub><jats:italic>k<\/jats:italic><\/jats:sub>) having girth (<jats:italic>H<\/jats:italic>) = <jats:italic>k<\/jats:italic> and the Ramsey property that every <jats:italic>r<\/jats:italic>-colouring of the edges of <jats:italic>H<\/jats:italic> yields a monochromatic <jats:italic>C<\/jats:italic><jats:sub><jats:italic>k<\/jats:italic><\/jats:sub> Two related numerical problems regarding arithmetic progressions in subsets of the integers and cliques in graphs are also considered.<\/jats:p>","DOI":"10.1017\/s0963548320000383","type":"journal-article","created":{"date-parts":[[2021,4,12]],"date-time":"2021-04-12T17:28:38Z","timestamp":1618248518000},"page":"722-740","update-policy":"http:\/\/dx.doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":1,"title":["Ramsey-type numbers involving graphs and hypergraphs with large girth"],"prefix":"10.1017","volume":"30","author":[{"given":"Hi\u00eap","family":"H\u00e0n","sequence":"first","affiliation":[]},{"given":"Troy","family":"Retter","sequence":"additional","affiliation":[]},{"given":"Vojt\u00each","family":"R\u00f6dl","sequence":"additional","affiliation":[]},{"given":"Mathias","family":"Schacht","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2021,4,12]]},"reference":[{"key":"S0963548320000383_ref12","doi-asserted-by":"crossref","first-page":"104","DOI":"10.1016\/S0021-9800(67)80119-4","article-title":"Research problems 2\u20135","volume":"2","author":"Erd\u0151s","year":"1967","journal-title":"J. Combin. Theory"},{"key":"S0963548320000383_ref11","doi-asserted-by":"publisher","DOI":"10.1007\/BF02020444"},{"key":"S0963548320000383_ref19","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(76)90015-0"},{"key":"S0963548320000383_ref7","first-page":"29","volume-title":"Theory of Graphs and its Applications","author":"Erd\u0151s","year":"1964"},{"key":"S0963548320000383_ref28","doi-asserted-by":"publisher","DOI":"10.1016\/S0021-9800(66)80054-6"},{"key":"S0963548320000383_ref13","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579234"},{"key":"S0963548320000383_ref15","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(86)90097-X"},{"key":"S0963548320000383_ref3","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/jdw010"},{"key":"S0963548320000383_ref23","doi-asserted-by":"publisher","DOI":"10.1007\/BF01787730"},{"key":"S0963548320000383_ref14","doi-asserted-by":"publisher","DOI":"10.1137\/0118004"},{"key":"S0963548320000383_ref17","unstructured":"[17] Jenssen, M. and Skokan, J. (2016) Exact Ramsey numbers of odd cycles via nonlinear optimisation. arXiv:1608.05705"},{"key":"S0963548320000383_ref4","doi-asserted-by":"publisher","DOI":"10.1016\/S0095-8956(73)80005-X"},{"key":"S0963548320000383_ref16","doi-asserted-by":"publisher","DOI":"10.1002\/9781118032718"},{"key":"S0963548320000383_ref20","first-page":"675","article-title":"Vander Waerden theorem for sequences of integers not containing an arithmetic progression of k terms","volume":"17","author":"Ne\u0161et\u0159il","year":"1976","journal-title":"Comment. Math. Univ. Carolinae"},{"key":"S0963548320000383_ref29","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(75)90053-9"},{"key":"S0963548320000383_ref22","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579159"},{"key":"S0963548320000383_ref24","doi-asserted-by":"publisher","DOI":"10.2307\/2152833"},{"key":"S0963548320000383_ref21","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579274"},{"key":"S0963548320000383_ref25","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-015-3298-1"},{"key":"S0963548320000383_ref10","unstructured":"[10] Erd\u0151s, P. and Graham, R. L. (1975) On partition theorems for finite graphs. In Infinite and Finite Sets I, Vol. 10 of Colloquia Mathematica Societatis J\u00e1nos Bolyai, pp. 515\u2013527. North-Holland."},{"key":"S0963548320000383_ref8","first-page":"295","article-title":"Problems and results in combinatorial number theory","volume":"24\u201325","author":"Erd\u0151s","year":"1975","journal-title":"Ast\u00e9risque"},{"key":"S0963548320000383_ref5","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(74)90052-5"},{"key":"S0963548320000383_ref6","first-page":"74","article-title":"On sequences of integers no one of which divides the product of two others and on some related problems","volume":"2","author":"Erd\u0151s","year":"1938","journal-title":"Mitt. Forsch.-Inst. Math. und Mech. Univ. Tomsk"},{"key":"S0963548320000383_ref2","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1966-109-8"},{"key":"S0963548320000383_ref1","doi-asserted-by":"publisher","DOI":"10.1090\/S0894-0347-2014-00816-X"},{"key":"S0963548320000383_ref18","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548314000832"},{"key":"S0963548320000383_ref26","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2011.174.1.20"},{"key":"S0963548320000383_ref9","first-page":"183","volume-title":"Recent Advances in Graph Theory","author":"Erd\u0151s","year":"1975"},{"key":"S0963548320000383_ref27","doi-asserted-by":"publisher","DOI":"10.1007\/s00222-014-0562-8"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548320000383","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,8,6]],"date-time":"2021-08-06T13:36:47Z","timestamp":1628257007000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548320000383\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,4,12]]},"references-count":29,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2021,9]]}},"alternative-id":["S0963548320000383"],"URL":"https:\/\/doi.org\/10.1017\/s0963548320000383","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,4,12]]},"assertion":[{"value":"\u00a9 The Author(s), 2021. Published by Cambridge University Press","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}}]}}