{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T01:14:34Z","timestamp":1777425274230,"version":"3.51.4"},"reference-count":11,"publisher":"Cambridge University Press (CUP)","issue":"6","license":[{"start":{"date-parts":[[2014,12,29]],"date-time":"2014-12-29T00:00:00Z","timestamp":1419811200000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2015,11]]},"abstract":"<jats:p>Over 50 years ago, Erd\u0151s and Gallai conjectured that the edges of every graph on <jats:italic>n<\/jats:italic> vertices can be decomposed into <jats:italic>O<\/jats:italic>(<jats:italic>n<\/jats:italic>) cycles and edges. Among other results, Conlon, Fox and Sudakov recently proved that this holds for the random graph <jats:italic>G<\/jats:italic>(<jats:italic>n, p<\/jats:italic>) with probability approaching 1 as <jats:italic>n<\/jats:italic> \u2192 \u221e. In this paper we show that for most edge probabilities <jats:italic>G<\/jats:italic>(<jats:italic>n, p<\/jats:italic>) can be decomposed into a union of <jats:italic>n<\/jats:italic>\/4 + <jats:italic>np<\/jats:italic>\/2 + <jats:italic>o<\/jats:italic>(<jats:italic>n<\/jats:italic>) cycles and edges w.h.p. This result is asymptotically tight.<\/jats:p>","DOI":"10.1017\/s0963548314000844","type":"journal-article","created":{"date-parts":[[2014,12,29]],"date-time":"2014-12-29T09:48:24Z","timestamp":1419846504000},"page":"857-872","source":"Crossref","is-referenced-by-count":6,"title":["Decomposing Random Graphs into Few Cycles and Edges"],"prefix":"10.1017","volume":"24","author":[{"given":"D\u00c1NIEL","family":"KOR\u00c1NDI","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"MICHAEL","family":"KRIVELEVICH","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"BENNY","family":"SUDAKOV","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2014,12,29]]},"reference":[{"key":"S0963548314000844_ref6","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20574"},{"key":"S0963548314000844_ref1","doi-asserted-by":"publisher","DOI":"10.1002\/9780470277331"},{"key":"S0963548314000844_ref2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511814068"},{"key":"S0963548314000844_ref9","doi-asserted-by":"crossref","unstructured":"Knox F. , K\u00fchn D. and Osthus D. Edge-disjoint Hamilton cycles in random graphs. Random Struct. Alg., to appear.","DOI":"10.1002\/rsa.20510"},{"key":"S0963548314000844_ref4","unstructured":"Broder A. Z. , Frieze A. M. , Suen S. and Upfal E. (1996) An efficient algorithm for the vertex-disjoint paths problem in random graphs. In Proc. Seventh Annual ACM\u2013SIAM Symposium on Discrete Algorithms: SODA '96, SIAM, pp. 261\u2013268."},{"key":"S0963548314000844_ref11","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579444"},{"key":"S0963548314000844_ref7","first-page":"3","article-title":"On some of my conjectures in number theory and combinatorics","volume":"39","author":"Erd\u0151s","year":"1983","journal-title":"Congr. Numer."},{"key":"S0963548314000844_ref10","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(76)90068-6"},{"key":"S0963548314000844_ref3","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-006-0002-5"},{"key":"S0963548314000844_ref8","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1966-014-3"},{"key":"S0963548314000844_ref5","doi-asserted-by":"publisher","DOI":"10.1006\/aama.2001.0720"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548314000844","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,20]],"date-time":"2019-04-20T02:25:54Z","timestamp":1555727154000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548314000844\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,12,29]]},"references-count":11,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2015,11]]}},"alternative-id":["S0963548314000844"],"URL":"https:\/\/doi.org\/10.1017\/s0963548314000844","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,12,29]]}}}