{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,10]],"date-time":"2026-04-10T15:36:39Z","timestamp":1775835399618,"version":"3.50.1"},"reference-count":38,"publisher":"Cambridge University Press (CUP)","issue":"3","license":[{"start":{"date-parts":[[2016,12,7]],"date-time":"2016-12-07T00:00:00Z","timestamp":1481068800000},"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":[[2017,5]]},"abstract":"<jats:p>Let<jats:italic>k<\/jats:italic>\u2a7e 3 be a fixed integer and let<jats:italic>Z<jats:sub>k<\/jats:sub><\/jats:italic>(<jats:italic>G<\/jats:italic>) be the number of<jats:italic>k<\/jats:italic>-colourings of the graph<jats:italic>G<\/jats:italic>. For certain values of the average degree, the random variable<jats:italic>Z<jats:sub>k<\/jats:sub><\/jats:italic>(<jats:italic>G<\/jats:italic>(<jats:italic>n<\/jats:italic>,<jats:italic>m<\/jats:italic>)) is known to be concentrated in the sense that<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0963548316000390_inline1\"\/><jats:tex-math>$\\tfrac{1}{n}(\\ln Z_k(G(n,m))-\\ln\\Erw[Z_k(G(n,m))])$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>converges to 0 in probability (Achlioptas and Coja-Oghlan,<jats:italic>Proc. FOCS 2008<\/jats:italic>). In the present paper we prove a significantly stronger concentration result. Namely, we show that for a wide range of average degrees,<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0963548316000390_inline2\"\/><jats:tex-math>$\\tfrac{1}{\\omega}(\\ln Z_k(G(n,m))-\\ln\\Erw[Z_k(G(n,m))])$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>converges to 0 in probability for<jats:italic>any<\/jats:italic>diverging function<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0963548316000390_inline3\"\/><jats:tex-math>$\\omega=\\omega(n)\\ra\\infty$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>. For<jats:italic>k<\/jats:italic>exceeding a certain constant<jats:italic>k<\/jats:italic><jats:sub>0<\/jats:sub>this result covers all average degrees up to the so-called<jats:italic>condensation phase transition<\/jats:italic><jats:italic>d<\/jats:italic><jats:italic><jats:sub>k,con<\/jats:sub><\/jats:italic>, and this is best possible. As an application, we show that the experiment of choosing a<jats:italic>k<\/jats:italic>-colouring of the random graph<jats:italic>G<\/jats:italic>(<jats:italic>n,m<\/jats:italic>) uniformly at random is contiguous with respect to the so-called \u2018planted model\u2019.<\/jats:p>","DOI":"10.1017\/s0963548316000390","type":"journal-article","created":{"date-parts":[[2016,12,7]],"date-time":"2016-12-07T07:51:51Z","timestamp":1481097111000},"page":"338-366","source":"Crossref","is-referenced-by-count":11,"title":["Planting Colourings Silently"],"prefix":"10.1017","volume":"26","author":[{"given":"VICTOR","family":"BAPST","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"AMIN","family":"COJA-OGHLAN","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"CHARILAOS","family":"EFTHYMIOU","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2016,12,7]]},"reference":[{"key":"S0963548316000390_ref9","doi-asserted-by":"publisher","DOI":"10.1007\/BF02122551"},{"key":"S0963548316000390_ref28","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579304"},{"key":"S0963548316000390_ref26","doi-asserted-by":"publisher","DOI":"10.1007\/BF01375472"},{"key":"S0963548316000390_ref16","doi-asserted-by":"crossref","unstructured":"Efthymiou C. (2014) Switching colouring of G(n, d\/n) for sampling up to Gibbs uniqueness threshold. In Proc. 22nd ESA, pp. 371\u2013281.","DOI":"10.1007\/978-3-662-44777-2_31"},{"key":"S0963548316000390_ref5","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2005.162.1335"},{"key":"S0963548316000390_ref3","doi-asserted-by":"crossref","unstructured":"Achlioptas D. and Molloy M. (1997) The analysis of a list-coloring algorithm on a random graph. In Proc. 38th FOCS, pp. 204\u2013212.","DOI":"10.1109\/SFCS.1997.646109"},{"key":"S0963548316000390_ref29","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-12788-9_6"},{"key":"S0963548316000390_ref17","first-page":"17","article-title":"On the evolution of random graphs.","volume":"5","author":"Erd\u0151s","year":"1960","journal-title":"Magyar Tud. Akad. Mat. Kutat\u00f3 Int. K\u00f6zl."},{"key":"S0963548316000390_ref21","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2009.08.006"},{"key":"S0963548316000390_ref35","unstructured":"Neeman J. and Netrapalli P. Non-reconstructability in the stochastic block model. arXiv:1404.6304"},{"key":"S0963548316000390_ref38","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.76.031131"},{"key":"S0963548316000390_ref2","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1098-2418(1999010)14:1<63::AID-RSA3>3.0.CO;2-7"},{"key":"S0963548316000390_ref37","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579208"},{"key":"S0963548316000390_ref33","doi-asserted-by":"publisher","DOI":"10.1137\/090755862"},{"key":"S0963548316000390_ref14","unstructured":"Coja-Oghlan A. and Panagiotou K. (2016) Going after the k-SAT threshold. In Proc. 45th STOC 2013, pp. 705\u2013714, and Adv. Math. 288 985\u20131068."},{"key":"S0963548316000390_ref30","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780198570837.001.0001"},{"key":"S0963548316000390_ref24","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.70.046705"},{"key":"S0963548316000390_ref4","doi-asserted-by":"crossref","unstructured":"Achlioptas D. and Moore C. (2004) The chromatic number of random regular graphs. In Proc. 8th RANDOM, pp. 219\u2013228.","DOI":"10.1007\/978-3-540-27821-4_20"},{"key":"S0963548316000390_ref1","doi-asserted-by":"crossref","unstructured":"Achlioptas D. and Coja-Oghlan A. (2008) Algorithmic barriers from phase transitions. In Proc. 49th FOCS, pp. 793\u2013802.","DOI":"10.1109\/FOCS.2008.11"},{"key":"S0963548316000390_ref18","doi-asserted-by":"publisher","DOI":"10.1017\/S0305004100051124"},{"key":"S0963548316000390_ref22","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(98)00092-1"},{"key":"S0963548316000390_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":"S0963548316000390_ref36","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240050209"},{"key":"S0963548316000390_ref27","doi-asserted-by":"publisher","DOI":"10.1007\/BF01205080"},{"key":"S0963548316000390_ref7","unstructured":"Banks J. and Moore C. Information-theoretic thresholds for community detection in sparse networks. arXiv:1601.02658"},{"key":"S0963548316000390_ref13","doi-asserted-by":"publisher","DOI":"10.1137\/110842867"},{"key":"S0963548316000390_ref10","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511814068"},{"key":"S0963548316000390_ref23","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0703685104"},{"key":"S0963548316000390_ref8","doi-asserted-by":"publisher","DOI":"10.1007\/s00220-015-2464-z"},{"key":"S0963548316000390_ref15","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.48"},{"key":"S0963548316000390_ref25","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.102.238701"},{"key":"S0963548316000390_ref31","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214060"},{"key":"S0963548316000390_ref6","doi-asserted-by":"publisher","DOI":"10.1007\/BF01215914"},{"key":"S0963548316000390_ref19","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548300001735"},{"key":"S0963548316000390_ref20","doi-asserted-by":"publisher","DOI":"10.1002\/9781118032718"},{"key":"S0963548316000390_ref12","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2015.09.006"},{"key":"S0963548316000390_ref32","doi-asserted-by":"crossref","unstructured":"Molloy M. and Restrepo R. (2013) Frozen variables in random boolean constraint satisfaction problems. In Proc. 24th SODA, pp. 1306\u20131318.","DOI":"10.1137\/1.9781611973105.95"},{"key":"S0963548316000390_ref34","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.89.268701"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548316000390","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,9,27]],"date-time":"2020-09-27T19:56:55Z","timestamp":1601236615000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548316000390\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,12,7]]},"references-count":38,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2017,5]]}},"alternative-id":["S0963548316000390"],"URL":"https:\/\/doi.org\/10.1017\/s0963548316000390","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,12,7]]}}}