{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,3]],"date-time":"2025-09-03T11:00:27Z","timestamp":1756897227677},"reference-count":30,"publisher":"Cambridge University Press (CUP)","issue":"1","license":[{"start":{"date-parts":[[2018,5,21]],"date-time":"2018-05-21T00:00:00Z","timestamp":1526860800000},"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":[[2019,1]]},"abstract":"<jats:p>Let<jats:italic>k<\/jats:italic>\u2a7e 3 be a fixed integer. We exactly determine the asymptotic distribution of ln<jats:italic>Z<jats:sub>k<\/jats:sub><\/jats:italic>(<jats:italic>G<\/jats:italic>(<jats:italic>n, m<\/jats:italic>)), where<jats:italic>Z<jats:sub>k<\/jats:sub><\/jats:italic>(<jats:italic>G<\/jats:italic>(<jats:italic>n, m<\/jats:italic>)) is the number of<jats:italic>k<\/jats:italic>-colourings of the random graph<jats:italic>G<\/jats:italic>(<jats:italic>n, m<\/jats:italic>). A crucial observation to this end is that the fluctuations in the number of colourings can be attributed to the fluctuations in the number of small cycles in<jats:italic>G<\/jats:italic>(<jats:italic>n, m<\/jats:italic>). Our result holds for a wide range of average degrees, and for<jats:italic>k<\/jats:italic>exceeding a certain constant<jats:italic>k<\/jats:italic><jats:sub>0<\/jats:sub>it covers all average degrees up to the so-called<jats:italic>condensation phase transition<\/jats:italic>.<\/jats:p>","DOI":"10.1017\/s0963548318000251","type":"journal-article","created":{"date-parts":[[2018,5,21]],"date-time":"2018-05-21T09:27:21Z","timestamp":1526894841000},"page":"130-158","source":"Crossref","is-referenced-by-count":6,"title":["On the Number of Solutions in Random Graph<i>k<\/i>-Colouring"],"prefix":"10.1017","volume":"28","author":[{"given":"FELICIA","family":"RASSMANN","sequence":"first","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2018,5,21]]},"reference":[{"key":"S0963548318000251_ref14","unstructured":"Coja-Oghlan A. and Wormald N. The number of satisfying assignments of random regular k-SAT formulas. arXiv:1611.03236"},{"key":"S0963548318000251_ref11","doi-asserted-by":"crossref","first-page":"P32","DOI":"10.37236\/3337","article-title":"Upper-bounding the k-colorability threshold by counting covers","volume":"20","author":"Coja-Oghlan","year":"2013","journal-title":"Electron. J. Combin."},{"key":"S0963548318000251_ref28","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240050209"},{"key":"S0963548318000251_ref3","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2005.162.1335"},{"key":"S0963548318000251_ref29","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579208"},{"key":"S0963548318000251_ref19","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0703685104"},{"key":"S0963548318000251_ref12","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2015.09.006"},{"key":"S0963548318000251_ref7","doi-asserted-by":"publisher","DOI":"10.1007\/s00220-015-2464-z"},{"key":"S0963548318000251_ref17","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548300001735"},{"key":"S0963548318000251_ref8","doi-asserted-by":"publisher","DOI":"10.1214\/15-AAP1119"},{"key":"S0963548318000251_ref18","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2009.08.006"},{"key":"S0963548318000251_ref25","doi-asserted-by":"publisher","DOI":"10.4171\/AIHPD\/31"},{"key":"S0963548318000251_ref4","doi-asserted-by":"publisher","DOI":"10.1007\/BF01215914"},{"key":"S0963548318000251_ref26","doi-asserted-by":"crossref","unstructured":"Rassmann F. (2017) The Electronic Journal of Combinatorics 24 (3) #P3.11.","DOI":"10.37236\/6029"},{"key":"S0963548318000251_ref22","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579304"},{"key":"S0963548318000251_ref1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.11"},{"key":"S0963548318000251_ref30","first-page":"239","volume-title":"Surveys in Combinatorics","author":"Wormald","year":"1999"},{"key":"S0963548318000251_ref10","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511814068"},{"key":"S0963548318000251_ref16","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9781316339831","volume-title":"Introduction to Random Graphs","author":"Frieze","year":"2015"},{"key":"S0963548318000251_ref23","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214060"},{"key":"S0963548318000251_ref21","doi-asserted-by":"publisher","DOI":"10.1007\/BF01375472"},{"key":"S0963548318000251_ref6","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548316000390"},{"key":"S0963548318000251_ref24","doi-asserted-by":"publisher","DOI":"10.1137\/090755862"},{"key":"S0963548318000251_ref15","first-page":"17","article-title":"On the evolution of random graphs","volume":"5","author":"Erd\u0151s","year":"1960","journal-title":"Magayar Tud. Akad. Mat. Kutato Int. Kozl."},{"key":"S0963548318000251_ref27","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240030202"},{"key":"S0963548318000251_ref20","doi-asserted-by":"publisher","DOI":"10.1007\/BF01205080"},{"key":"S0963548318000251_ref5","first-page":"383","volume-title":"COLT: 29th Conference on Learning Theory","author":"Banks","year":"2016"},{"key":"S0963548318000251_ref13","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.48"},{"key":"S0963548318000251_ref9","doi-asserted-by":"publisher","DOI":"10.1007\/BF02122551"},{"key":"S0963548318000251_ref2","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1098-2418(1999010)14:1<63::AID-RSA3>3.0.CO;2-7"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548318000251","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,8,23]],"date-time":"2022-08-23T23:16:46Z","timestamp":1661296606000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548318000251\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,5,21]]},"references-count":30,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2019,1]]}},"alternative-id":["S0963548318000251"],"URL":"https:\/\/doi.org\/10.1017\/s0963548318000251","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"type":"print","value":"0963-5483"},{"type":"electronic","value":"1469-2163"}],"subject":[],"published":{"date-parts":[[2018,5,21]]}}}