{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,27]],"date-time":"2025-06-27T18:41:47Z","timestamp":1751049707794},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2024,5,14]],"date-time":"2024-05-14T00:00:00Z","timestamp":1715644800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,5,14]],"date-time":"2024-05-14T00:00:00Z","timestamp":1715644800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Swiss Federal Institute of Technology Zurich"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Combinatorica"],"published-print":{"date-parts":[[2024,10]]},"abstract":"Abstract<\/jats:title>The induced size-Ramsey number $$\\hat{r}_\\text {ind}^k(H)$$<\/jats:tex-math>\n \n \n \n r<\/mml:mi>\n ^<\/mml:mo>\n <\/mml:mover>\n ind<\/mml:mtext>\n k<\/mml:mi>\n <\/mml:msubsup>\n \n (<\/mml:mo>\n H<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> of a graph H<\/jats:italic> is the smallest number of edges a (host) graph G<\/jats:italic> can have such that for any k<\/jats:italic>-coloring of its edges, there exists a monochromatic copy of H<\/jats:italic> which is an induced subgraph of G<\/jats:italic>. In 1995, in their seminal paper, Haxell, Kohayakawa and \u0141uczak showed that for cycles, these numbers are linear for any constant number of colours, i.e., $$\\hat{r}_\\text {ind}^k(C_n)\\le Cn$$<\/jats:tex-math>\n \n \n \n r<\/mml:mi>\n ^<\/mml:mo>\n <\/mml:mover>\n ind<\/mml:mtext>\n k<\/mml:mi>\n <\/mml:msubsup>\n \n (<\/mml:mo>\n \n C<\/mml:mi>\n n<\/mml:mi>\n <\/mml:msub>\n )<\/mml:mo>\n <\/mml:mrow>\n \u2264<\/mml:mo>\n C<\/mml:mi>\n n<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> for some $$C=C(k)$$<\/jats:tex-math>\n \n C<\/mml:mi>\n =<\/mml:mo>\n C<\/mml:mi>\n (<\/mml:mo>\n k<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. The constant C<\/jats:italic> comes from the use of the regularity lemma, and has a tower type dependence on k<\/jats:italic>. In this paper we significantly improve these bounds, showing that $$\\hat{r}_\\text {ind}^k(C_n)\\le O(k^{102})n$$<\/jats:tex-math>\n \n \n \n r<\/mml:mi>\n ^<\/mml:mo>\n <\/mml:mover>\n ind<\/mml:mtext>\n k<\/mml:mi>\n <\/mml:msubsup>\n \n (<\/mml:mo>\n \n C<\/mml:mi>\n n<\/mml:mi>\n <\/mml:msub>\n )<\/mml:mo>\n <\/mml:mrow>\n \u2264<\/mml:mo>\n O<\/mml:mi>\n \n (<\/mml:mo>\n \n k<\/mml:mi>\n 102<\/mml:mn>\n <\/mml:msup>\n )<\/mml:mo>\n <\/mml:mrow>\n n<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> when n<\/jats:italic> is even, thus obtaining only a polynomial dependence of C<\/jats:italic> on k<\/jats:italic>. We also prove $$\\hat{r}_\\text {ind}^k(C_n)\\le e^{O(k\\log k)}n$$<\/jats:tex-math>\n \n \n \n r<\/mml:mi>\n ^<\/mml:mo>\n <\/mml:mover>\n ind<\/mml:mtext>\n k<\/mml:mi>\n <\/mml:msubsup>\n \n (<\/mml:mo>\n \n C<\/mml:mi>\n n<\/mml:mi>\n <\/mml:msub>\n )<\/mml:mo>\n <\/mml:mrow>\n \u2264<\/mml:mo>\n \n e<\/mml:mi>\n \n O<\/mml:mi>\n (<\/mml:mo>\n k<\/mml:mi>\n log<\/mml:mo>\n k<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:msup>\n n<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> for odd n<\/jats:italic>, which almost matches the lower bound of $$e^{\\Omega (k)}n$$<\/jats:tex-math>\n \n \n e<\/mml:mi>\n \n \u03a9<\/mml:mi>\n (<\/mml:mo>\n k<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:msup>\n n<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. Finally, we show that the ordinary (non-induced) size-Ramsey number satisfies $$\\hat{r}^k(C_n)=e^{O(k)}n$$<\/jats:tex-math>\n \n \n \n r<\/mml:mi>\n ^<\/mml:mo>\n <\/mml:mover>\n k<\/mml:mi>\n <\/mml:msup>\n \n (<\/mml:mo>\n \n C<\/mml:mi>\n n<\/mml:mi>\n <\/mml:msub>\n )<\/mml:mo>\n <\/mml:mrow>\n =<\/mml:mo>\n \n e<\/mml:mi>\n \n O<\/mml:mi>\n (<\/mml:mo>\n k<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:msup>\n n<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> for odd n<\/jats:italic>. This substantially improves the best previous result of $$e^{O(k^2)}n$$<\/jats:tex-math>\n \n \n e<\/mml:mi>\n \n O<\/mml:mi>\n (<\/mml:mo>\n \n k<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msup>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:msup>\n n<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, and is best possible, up to the implied constant in the exponent. To achieve our results, we present a new host graph construction which, roughly speaking, reduces our task to finding a cycle of approximate given length in a graph with local sparsity.<\/jats:p>","DOI":"10.1007\/s00493-024-00103-5","type":"journal-article","created":{"date-parts":[[2024,5,14]],"date-time":"2024-05-14T10:01:43Z","timestamp":1715680903000},"page":"1011-1039","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Effective Bounds for Induced Size-Ramsey Numbers of Cycles"],"prefix":"10.1007","volume":"44","author":[{"given":"Domagoj","family":"Brada\u010d","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nemanja","family":"Dragani\u0107","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Benny","family":"Sudakov","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,5,14]]},"reference":[{"key":"103_CR1","doi-asserted-by":"publisher","first-page":"R12","DOI":"10.37236\/1192","volume":"1","author":"N Alon","year":"1994","unstructured":"Alon, N.: Explicit Ramsey graphs and orthonormal labelings. Electron. J. Comb. 1, R12\u2013R12 (1994)","journal-title":"Electron. J. Comb."},{"issue":"1","key":"103_CR2","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1002\/jgt.3190070115","volume":"7","author":"J Beck","year":"1983","unstructured":"Beck, J.: On size Ramsey number of paths, trees, and circuits. I. J. Graph Theory 7(1), 115\u2013129 (1983)","journal-title":"J. Graph Theory"},{"issue":"4","key":"103_CR3","doi-asserted-by":"publisher","first-page":"1314","DOI":"10.1112\/jlms.12408","volume":"103","author":"S Berger","year":"2021","unstructured":"Berger, S., Kohayakawa, Y., Maesaka, G.S., Martins, T., Mendon\u00e7a, W., Mota, G.O., Parczyk, O.: The size-Ramsey number of powers of bounded degree trees. J. Lond. Math. Soc. 103(4), 1314\u20131332 (2021)","journal-title":"J. Lond. Math. Soc."},{"issue":"2","key":"103_CR4","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1016\/0095-8956(74)90052-5","volume":"16","author":"JA Bondy","year":"1974","unstructured":"Bondy, J.A., Simonovits, M.: Cycles of even length in graphs. J. Comb. Theory Ser. B 16(2), 97\u2013105 (1974)","journal-title":"J. Comb. Theory Ser. B"},{"issue":"2","key":"103_CR5","doi-asserted-by":"publisher","first-page":"513","DOI":"10.1007\/s00493-012-2710-3","volume":"32","author":"D Conlon","year":"2012","unstructured":"Conlon, D., Fox, J., Sudakov, B.: On two problems in graph Ramsey theory. Combinatorica 32(2), 513\u2013535 (2012)","journal-title":"Combinatorica"},{"key":"103_CR6","first-page":"49","volume-title":"Surveys in Combinatorics","author":"D Conlon","year":"2015","unstructured":"Conlon, D., Fox, J., Sudakov, B.: Recent developments in graph Ramsey theory. In: Bailey, R. (ed.) Surveys in Combinatorics, pp. 49\u2013118. Cambridge University Press, Cambridge (2015)"},{"key":"103_CR7","unstructured":"Deuber, W.: A generalization of Ramsey\u2019s theorem. In: Infinite and Finite Sets, Vol. 1, Colloquia Mathematica Societatis J\u00e1nos Bolyai, Vol. 10, pp. 323\u2013332. North-Holland, Amsterdam\/London (1975)"},{"key":"103_CR8","unstructured":"Dragani\u0107, N., Petrova, K.: Size-Ramsey numbers of graphs with maximum degree three. (2022) arXiv:2207.05048"},{"issue":"5","key":"103_CR9","doi-asserted-by":"publisher","first-page":"870","DOI":"10.1017\/S0963548322000013","volume":"31","author":"N Dragani\u0107","year":"2022","unstructured":"Dragani\u0107, N., Glock, S., Krivelevich, M.: Short proofs for long induced paths. Comb. Probab. Comput. 31(5), 870\u2013878 (2022)","journal-title":"Comb. Probab. Comput."},{"issue":"7","key":"103_CR10","doi-asserted-by":"publisher","first-page":"5195","DOI":"10.1090\/tran\/8660","volume":"375","author":"N Dragani\u0107","year":"2022","unstructured":"Dragani\u0107, N., Krivelevich, M., Nenadov, R.: Rolling backwards can move you forward: on embedding problems in sparse expanders. Trans. Am. Math. Soc. 375(7), 5195\u2013216 (2022)","journal-title":"Trans. Am. Math. Soc."},{"issue":"3","key":"103_CR11","doi-asserted-by":"publisher","first-page":"551","DOI":"10.1017\/S096354831400056X","volume":"24","author":"A Dudek","year":"2015","unstructured":"Dudek, A., Pra\u0142at, P.: An alternative proof of the linearity of the size-Ramsey number of paths. Comb. Probab. Comput. 24(3), 551\u2013555 (2015)","journal-title":"Comb. Probab. Comput."},{"issue":"3","key":"103_CR12","doi-asserted-by":"publisher","first-page":"2079","DOI":"10.1137\/16M1069717","volume":"31","author":"A Dudek","year":"2017","unstructured":"Dudek, A., Pra\u0142at, P.: On some multicolor Ramsey properties of random graphs. SIAM J. Discret. Math. 31(3), 2079\u20132092 (2017)","journal-title":"SIAM J. Discret. Math."},{"key":"103_CR13","first-page":"623","volume":"7","author":"P Erd\u0151s","year":"1962","unstructured":"Erd\u0151s, P., R\u00e9nyi, A.: On a problem in the theory of graphs A Magyar Tudom\u00e1nyos Akad\u00e9mia. Matematikai Kutat\u00f3 Int\u00e9zet\u00e9nek K\u00f6zlem\u00e9nyei 7, 623\u2013641 (1962)","journal-title":"Matematikai Kutat\u00f3 Int\u00e9zet\u00e9nek K\u00f6zlem\u00e9nyei"},{"key":"103_CR14","unstructured":"Erd\u0151s, P., Hajnal, A., P\u00f3sa, L.: Strong embeddings of graphs into colored graphs. In: Infinite and Finite Sets, vol. 1, Colloquia Mathematica Societatis J\u00e1nos Bolyai, vol. 10, pp. 585\u2013595. North-Holland, Amsterdam\/London (1975)"},{"issue":"1\u20132","key":"103_CR15","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1007\/BF02018930","volume":"9","author":"P Erd\u0151s","year":"1978","unstructured":"Erd\u0151s, P., Faudree, R.J., Rousseau, C.C., Schelp, R.H.: The size Ramsey number. Period. Math. Hung. 9(1\u20132), 145\u2013161 (1978)","journal-title":"Period. Math. Hung."},{"issue":"6","key":"103_CR16","doi-asserted-by":"publisher","first-page":"1771","DOI":"10.1016\/j.aim.2008.07.009","volume":"219","author":"J Fox","year":"2008","unstructured":"Fox, J., Sudakov, B.: Induced Ramsey-type theorems. Adv. Math. 219(6), 1771\u20131800 (2008)","journal-title":"Adv. Math."},{"issue":"1","key":"103_CR17","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1007\/BF02579202","volume":"7","author":"J Friedman","year":"1987","unstructured":"Friedman, J., Pippenger, N.: Expanding graphs contain all small trees. Combinatorica 7(1), 71\u201376 (1987)","journal-title":"Combinatorica"},{"issue":"3","key":"103_CR18","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1017\/S0963548300001619","volume":"4","author":"PE Haxell","year":"1995","unstructured":"Haxell, P.E., Kohayakawa, Y., \u0141uczak, T.: The induced size-Ramsey number of cycles. Comb. Probab. Comput. 4(3), 217\u2013239 (1995)","journal-title":"Comb. Probab. Comput."},{"key":"103_CR19","volume-title":"Random graphs","author":"S Janson","year":"2011","unstructured":"Janson, S., \u0141uczak, T., Ruci\u0144ski, A.: Random graphs. Wiley, Hoboken (2011)"},{"key":"103_CR20","doi-asserted-by":"publisher","first-page":"264","DOI":"10.1016\/j.jctb.2022.10.003","volume":"158","author":"R Javadi","year":"2023","unstructured":"Javadi, R., Miralaei, M.: The multicolor size-Ramsey numbers of cycles. J. Comb. Theory Ser. B 158, 264\u2013285 (2023)","journal-title":"J. Comb. Theory Ser. B"},{"issue":"6","key":"103_CR21","doi-asserted-by":"publisher","first-page":"871","DOI":"10.1017\/S0963548319000221","volume":"28","author":"R Javadi","year":"2019","unstructured":"Javadi, R., Khoeini, F., Omidi, G.R., Pokrovskiy, A.: On the size-Ramsey number of cycles. Comb. Probab. Comput. 28(6), 871\u2013880 (2019)","journal-title":"Comb. Probab. Comput."},{"issue":"1","key":"103_CR22","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1137\/20M1335790","volume":"35","author":"N Kam\u010dev","year":"2021","unstructured":"Kam\u010dev, N., Liebenau, A., Wood, D.R., Yepremyan, L.: The size Ramsey number of graphs with bounded treewidth. SIAM J. Discret. Math. 35(1), 281\u2013293 (2021)","journal-title":"SIAM J. Discret. Math."},{"issue":"3","key":"103_CR23","doi-asserted-by":"publisher","first-page":"373","DOI":"10.1007\/PL00009828","volume":"18","author":"Y Kohayakawa","year":"1998","unstructured":"Kohayakawa, Y., Promel, H.J., R\u00f6dl, V.: Induced Ramsey numbers. Combinatorica 18(3), 373\u2013404 (1998)","journal-title":"Combinatorica"},{"issue":"6","key":"103_CR24","doi-asserted-by":"publisher","first-page":"5041","DOI":"10.1016\/j.aim.2011.01.004","volume":"226","author":"Y Kohayakawa","year":"2011","unstructured":"Kohayakawa, Y., R\u00f6dl, V., Schacht, M., Szemer\u00e9di, E.: Sparse partition universal graphs for graphs of bounded degree. Adv. Math. 226(6), 5041\u20135065 (2011)","journal-title":"Adv. Math."},{"key":"103_CR25","doi-asserted-by":"crossref","unstructured":"Krivelevich, M., Sudakov, B.: Pseudo-random graphs. In: More sets, graphs and numbers, pp. 199\u2013262. Springer, Cham (2006)","DOI":"10.1007\/978-3-540-32439-3_10"},{"key":"103_CR26","doi-asserted-by":"crossref","unstructured":"Krivelevich, M.: Expanders\u2013how to find them, and what to find in them. In: Surveys in combinatorics 2019. volume 456 of London Mathematical Society Lecture Note Series, pp. 115\u2013142. Cambridge University Press, Cambridge (2019)","DOI":"10.1017\/9781108649094.005"},{"issue":"1","key":"103_CR27","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1007\/s00493-017-3701-1","volume":"39","author":"M Krivelevich","year":"2019","unstructured":"Krivelevich, M.: Long cycles in locally expanding graphs, with applications. Combinatorica 39(1), 135\u2013151 (2019)","journal-title":"Combinatorica"},{"key":"103_CR28","unstructured":"Paul, E.: Problems and results on finite and infinite graphs. In: Recent Advances in Graph Theory. Proceedings of the Second Czechoslovak Symposium, pp. 183\u2013192. Academia, Prague (1975)"},{"issue":"4","key":"103_CR29","first-page":"264","volume":"30","author":"FP Ramsey","year":"1929","unstructured":"Ramsey, F.P.: On a problem of formal logic. Proc. Lond. Math. Soc. 30(4), 264\u2013286 (1929)","journal-title":"Proc. Lond. Math. Soc."},{"key":"103_CR30","unstructured":"R\u00f6dl, V.: The dimension of a graph and generalized Ramsey theorems. Master\u2019s thesis, Charles University (1973)"},{"issue":"2","key":"103_CR31","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1007\/s004930070024","volume":"20","author":"V R\u00f6dl","year":"2000","unstructured":"R\u00f6dl, V., Szemer\u00e9di, E.: On size Ramsey numbers of graphs with bounded degree. Combinatorica 20(2), 257\u2013262 (2000)","journal-title":"Combinatorica"},{"key":"103_CR32","doi-asserted-by":"crossref","unstructured":"Tikhomirov, K.: On bounded degree graphs with large size-Ramsey numbers. (2022). arXiv:2210.05818","DOI":"10.1007\/s00493-023-00056-1"}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-024-00103-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00493-024-00103-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-024-00103-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,7]],"date-time":"2024-10-07T12:08:36Z","timestamp":1728302916000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00493-024-00103-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,5,14]]},"references-count":32,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2024,10]]}},"alternative-id":["103"],"URL":"https:\/\/doi.org\/10.1007\/s00493-024-00103-5","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"type":"print","value":"0209-9683"},{"type":"electronic","value":"1439-6912"}],"subject":[],"published":{"date-parts":[[2024,5,14]]},"assertion":[{"value":"6 February 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 February 2024","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 March 2024","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 May 2024","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}