{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,18]],"date-time":"2025-12-18T09:21:20Z","timestamp":1766049680704,"version":"build-2065373602"},"reference-count":19,"publisher":"Cambridge University Press (CUP)","issue":"1","license":[{"start":{"date-parts":[[2021,6,14]],"date-time":"2021-06-14T00:00:00Z","timestamp":1623628800000},"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":[[2022,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>A graph <jats:italic>G arrows<\/jats:italic> a graph <jats:italic>H<\/jats:italic> if in every 2-edge-colouring of <jats:italic>G<\/jats:italic> there exists a monochromatic copy of <jats:italic>H<\/jats:italic>. Schelp had the idea that if the complete graph <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548321000201_inline1.png\"\/><jats:tex-math>\n$K_n$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> arrows a small graph <jats:italic>H<\/jats:italic>, then every \u2018dense\u2019 subgraph of <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548321000201_inline2.png\"\/><jats:tex-math>\n$K_n$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> also arrows <jats:italic>H<\/jats:italic>, and he outlined some problems in this direction. Our main result is in this spirit. We prove that for every sufficiently large <jats:italic>n<\/jats:italic>, if <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548321000201_inline3.png\"\/><jats:tex-math>\n$n = 3t+r$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> where <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548321000201_inline4.png\"\/><jats:tex-math>\n$r \\in \\{0,1,2\\}$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> and <jats:italic>G<\/jats:italic> is an <jats:italic>n<\/jats:italic>-vertex graph with <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548321000201_inline5.png\"\/><jats:tex-math>\n$\\delta(G) \\ge (3n-1)\/4$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, then for every 2-edge-colouring of <jats:italic>G<\/jats:italic>, either there are cycles of every length <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548321000201_inline6.png\"\/><jats:tex-math>\n$\\{3, 4, 5, \\dots, 2t+r\\}$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> of the same colour, or there are cycles of every even length <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548321000201_inline7.png\"\/><jats:tex-math>\n$\\{4, 6, 8, \\dots, 2t+2\\}$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> of the samecolour.<\/jats:p><jats:p>Our result is tight in the sense that no longer cycles (of length <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548321000201_inline8.png\"\/><jats:tex-math>\n$&gt;2t+r$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>) can be guaranteed and the minimum degree condition cannot be reduced. It also implies the conjecture of Schelp that for every sufficiently large <jats:italic>n<\/jats:italic>, every <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548321000201_inline9.png\"\/><jats:tex-math>\n$(3t-1)$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>-vertex graph <jats:italic>G<\/jats:italic> with minimum degree larger than <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548321000201_inline10.png\"\/><jats:tex-math>\n$3|V(G)|\/4$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> arrows the path <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548321000201_inline11.png\"\/><jats:tex-math>\n$P_{2n}$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> with 2<jats:italic>n<\/jats:italic> vertices. Moreover, it implies for sufficiently large <jats:italic>n<\/jats:italic> the conjecture by Benevides, \u0141uczak, Scott, Skokan and White that for <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548321000201_inline12.png\"\/><jats:tex-math>\n$n=3t+r$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> where <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548321000201_inline13.png\"\/><jats:tex-math>\n$r \\in \\{0,1,2\\}$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> and every <jats:italic>n<\/jats:italic>-vertex graph G with <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548321000201_inline14.png\"\/><jats:tex-math>\n$\\delta(G) \\ge 3n\/4$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, in each 2-edge-colouring of <jats:italic>G<\/jats:italic> there exists a monochromatic cycle of length at least <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548321000201_inline15.png\"\/><jats:tex-math>\n$2t+r$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>.<\/jats:p>","DOI":"10.1017\/s0963548321000201","type":"journal-article","created":{"date-parts":[[2021,6,14]],"date-time":"2021-06-14T09:36:21Z","timestamp":1623663381000},"page":"109-122","update-policy":"https:\/\/doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":5,"title":["Monochromatic paths and cycles in 2-edge-coloured graphs with large minimum degree"],"prefix":"10.1017","volume":"31","author":[{"given":"J\u00f3zsef","family":"Balogh","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alexandr","family":"Kostochka","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mikhail","family":"Lavrov","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xujun","family":"Liu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2021,6,14]]},"reference":[{"key":"S0963548321000201_ref19","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.22052"},{"key":"S0963548321000201_ref13","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(81)90050-2"},{"key":"S0963548321000201_ref11","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.20231"},{"key":"S0963548321000201_ref16","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1998.1874"},{"key":"S0963548321000201_ref12","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548311000599"},{"key":"S0963548321000201_ref18","unstructured":"[18] Szemer\u00e9di, E. (1978) Regular partitions of graphs. Probl\u00e8mes combinatoires et th\u00e9orie des graphes (Colloq. Internat. CNRS, Univ. Orsay, Orsay, 1976), pp. 399\u2013401, Colloq. Internat. CNRS, 260, CNRS, Paris."},{"key":"S0963548321000201_ref5","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(71)90016-5"},{"key":"S0963548321000201_ref8","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2006.09.001"},{"key":"S0963548321000201_ref3","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548312000090"},{"key":"S0963548321000201_ref6","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(74)90052-5"},{"key":"S0963548321000201_ref4","unstructured":"[4] Berge, C. (1976) Graphs and Hypergraphs. Translated from the French by Edward Minieka. Second revised edition. North-Holland Mathematical Library, Vol. 6, North-Holland Publishing Co., Amsterdam-London; American Elsevier Publishing Co., Inc., New York, pp. ix+528."},{"key":"S0963548321000201_ref17","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2011.09.015"},{"key":"S0963548321000201_ref15","first-page":"187","article-title":"A new type of Ramsey\u2013Tur\u00e1n problems","volume":"272","author":"Li","year":"2010","journal-title":"Discrete Math."},{"key":"S0963548321000201_ref9","first-page":"167","article-title":"On Ramsey-type problems","volume":"10","author":"Gerencs\u00e9r","year":"1967","journal-title":"Ann. Sci. Budapest. E\u00f6tv\u00f6s Sect. Math."},{"key":"S0963548321000201_ref2","doi-asserted-by":"crossref","first-page":"55","DOI":"10.2140\/moscow.2020.9.55","article-title":"Long monochromatic paths and cycles in 2-edge-colored multipartite graphs","volume":"9","author":"Balogh","year":"2020","journal-title":"Moscow J. Comb. Number Theory"},{"key":"S0963548321000201_ref10","doi-asserted-by":"publisher","DOI":"10.1007\/BF02018591"},{"key":"S0963548321000201_ref1","unstructured":"[1] Bagga, K. and Varma, B. (1991) Bipartite graphs and degree conditions. In Graph Theory, Combinatorics, Algorithms and Applications, Proceedings of the 2nd International Conference, San Francisco, CA, 1989, pp. 564\u2013573."},{"key":"S0963548321000201_ref7","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(72)90020-2"},{"key":"S0963548321000201_ref14","doi-asserted-by":"publisher","DOI":"10.1007\/BF01196135"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548321000201","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,12,20]],"date-time":"2021-12-20T10:39:04Z","timestamp":1639996744000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548321000201\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,14]]},"references-count":19,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2022,1]]}},"alternative-id":["S0963548321000201"],"URL":"https:\/\/doi.org\/10.1017\/s0963548321000201","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"type":"print","value":"0963-5483"},{"type":"electronic","value":"1469-2163"}],"subject":[],"published":{"date-parts":[[2021,6,14]]},"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"}}]}}