{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,7,26]],"date-time":"2024-07-26T20:32:14Z","timestamp":1722025934308},"reference-count":25,"publisher":"Cambridge University Press (CUP)","issue":"1","license":[{"start":{"date-parts":[[2020,8,14]],"date-time":"2020-08-14T00:00:00Z","timestamp":1597363200000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2021,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Erd\u0151s, Gy\u00e1rf\u00e1s and Pyber showed that every <jats:italic>r<\/jats:italic>-edge-coloured complete graph <jats:italic>K<\/jats:italic><jats:sub><jats:italic>n<\/jats:italic><\/jats:sub> can be covered by 25 <jats:italic>r<\/jats:italic><jats:sup>2<\/jats:sup> log <jats:italic>r<\/jats:italic> vertex-disjoint monochromatic cycles (independent of <jats:italic>n<\/jats:italic>). Here we extend their result to the setting of binomial random graphs. That is, we show that if <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548320000401_inline1.png\" \/><jats:tex-math>\n$p  = p(n) = \\Omega(n^{-1\/(2r)})$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, then with high probability any <jats:italic>r<\/jats:italic>-edge-coloured <jats:italic>G<\/jats:italic>(<jats:italic>n<\/jats:italic>, <jats:italic>p<\/jats:italic>) can be covered by at most 1000<jats:italic>r<\/jats:italic><jats:sup>4<\/jats:sup> log <jats:italic>r<\/jats:italic> vertex-disjoint monochromatic cycles. This answers a question of Kor\u00e1ndi, Mousset, Nenadov, \u0160kori\u0107 and Sudakov.<\/jats:p>","DOI":"10.1017\/s0963548320000401","type":"journal-article","created":{"date-parts":[[2020,8,14]],"date-time":"2020-08-14T01:57:33Z","timestamp":1597370253000},"page":"136-152","update-policy":"http:\/\/dx.doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":3,"title":["Monochromatic cycle partitions in random graphs"],"prefix":"10.1017","volume":"30","author":[{"given":"Richard","family":"Lang","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Allan","family":"Lo","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2020,8,14]]},"reference":[{"key":"S0963548320000401_ref13","doi-asserted-by":"crossref","first-page":"P53","DOI":"10.37236\/540","article-title":"Partitioning 3-colored complete graphs into three monochromatic cycles","volume":"18","author":"Gy\u00e1rf\u00e1s","year":"2011","journal-title":"Electron. J. Combin."},{"key":"S0963548320000401_ref7","unstructured":"[7] Conlon, D. (2014) Combinatorial theorems relative to a random set. arXiv:1404.3324"},{"key":"S0963548320000401_ref6","unstructured":"[6] Buci\u0107, M. , Kor\u00e1ndi, D. and Sudakov, B. (2019) Covering random graphs by monochromatic trees and Helly-type results for hypergraphs. arXiv:1902.05055"},{"key":"S0963548320000401_ref17","doi-asserted-by":"crossref","unstructured":"[17] Kor\u00e1ndi, D. , Lang, R. , Letzter, S. and Pokrovskiy, A. (2020) Minimum degree conditions for monochromatic cycle partitioning, to appear in J. Combin. Theory Ser. B.","DOI":"10.1016\/j.jctb.2020.07.005"},{"key":"S0963548320000401_ref2","unstructured":"[2] Bal, D. and DeBiasio, L. Personal communication."},{"key":"S0963548320000401_ref3","doi-asserted-by":"crossref","first-page":"P1.18","DOI":"10.37236\/6089","article-title":"Partitioning random graphs into monochromatic components.","volume":"24","author":"Bal","year":"2017","journal-title":"Electron. J. Combin."},{"key":"S0963548320000401_ref11","first-page":"129","article-title":"Monochromatic path covers in nearly complete graphs","volume":"25","author":"Gy\u00e1rf\u00e1s","year":"1997","journal-title":"J. Combin. Math. Combin. Comput."},{"key":"S0963548320000401_ref21","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1998.1874"},{"key":"S0963548320000401_ref14","doi-asserted-by":"crossref","first-page":"210","DOI":"10.1006\/jctb.1997.1737","article-title":"Partitioning complete bipartite graphs by monochromatic cycles","volume":"69","author":"Haxell","year":"1997","journal-title":"J. Combin. Theory Ser. B"},{"key":"S0963548320000401_ref12","doi-asserted-by":"crossref","first-page":"855","DOI":"10.1016\/j.jctb.2006.02.007","article-title":"An improved bound for the monochromatic cycle partition number","volume":"96","author":"Gy\u00e1rf\u00e1s","year":"2006","journal-title":"J. Combin. Theory Ser. B"},{"key":"S0963548320000401_ref22","doi-asserted-by":"crossref","first-page":"423","DOI":"10.1017\/S0963548398003599","article-title":"Partitioning two-colored complete graphs into two monochromatic cycles","volume":"7","author":"\u0141uczak","year":"1998","journal-title":"Combin. Probab. Comput."},{"key":"S0963548320000401_ref23","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2014.01.003"},{"key":"S0963548320000401_ref25","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1002\/jgt.20492","article-title":"Monochromatic cycle partitions of edge-colored graphs","volume":"66","author":"S\u00e1rk\u00f6zy","year":"2011","journal-title":"J. Graph Theory"},{"key":"S0963548320000401_ref24","doi-asserted-by":"publisher","DOI":"10.2307\/2152833"},{"key":"S0963548320000401_ref10","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2015.07.007"},{"key":"S0963548320000401_ref4","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-014-2935-4"},{"key":"S0963548320000401_ref18","doi-asserted-by":"crossref","first-page":"667","DOI":"10.1002\/rsa.20819","article-title":"Monochromatic cycle covers in random graphs","volume":"53","author":"Kor\u00e1ndi","year":"2018","journal-title":"Random Struct. Algorithms"},{"key":"S0963548320000401_ref5","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2009.07.001"},{"key":"S0963548320000401_ref19","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2016.09.003"},{"key":"S0963548320000401_ref16","doi-asserted-by":"publisher","DOI":"10.1017\/S0305004117000846"},{"key":"S0963548320000401_ref9","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(91)90007-7"},{"key":"S0963548320000401_ref1","unstructured":"[1] Allen, P. , B\u00f6ttcher, J. , H\u00e0n, H. , Kohayakawa, Y. and Person, Y. (2016) Blow-up lemmas for sparse graphs. arXiv:1612.00622"},{"key":"S0963548320000401_ref8","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2016.08.006"},{"key":"S0963548320000401_ref20","unstructured":"[20] Letzter, S. (2015) Monochromatic cycle partitions of 2-coloured graphs with minimum degree 3n\/4. arXiv:1502.07736"},{"key":"S0963548320000401_ref15","doi-asserted-by":"crossref","DOI":"10.1002\/9781118032718","volume-title":"Random Graphs","author":"Janson","year":"2000"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548320000401","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,1,21]],"date-time":"2021-01-21T11:51:08Z","timestamp":1611229868000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548320000401\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,8,14]]},"references-count":25,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,1]]}},"alternative-id":["S0963548320000401"],"URL":"https:\/\/doi.org\/10.1017\/s0963548320000401","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,8,14]]},"assertion":[{"value":"\u00a9 The Author(s), 2020. 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 (http:\/\/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"}]}}