{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,2]],"date-time":"2022-04-02T23:33:53Z","timestamp":1648942433960},"reference-count":26,"publisher":"Cambridge University Press (CUP)","issue":"4","license":[{"start":{"date-parts":[[2020,6,22]],"date-time":"2020-06-22T00:00:00Z","timestamp":1592784000000},"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":[[2020,7]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>In this paper we propose a polynomial-time <jats:italic>deterministic<\/jats:italic> algorithm for approximately counting the <jats:italic>k<\/jats:italic>-colourings of the random graph <jats:italic>G<\/jats:italic>(<jats:italic>n, d\/n<\/jats:italic>), for constant <jats:italic>d<\/jats:italic>&gt;0. In particular, our algorithm computes in polynomial time a <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548320000255_inline1.png\" \/><jats:tex-math>\n$(1\\pm n^{-\\Omega(1)})$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>-approximation of the so-called \u2018free energy\u2019 of the <jats:italic>k<\/jats:italic>-colourings of <jats:italic>G<\/jats:italic>(<jats:italic>n, d\/n<\/jats:italic>), for <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548320000255_inline2.png\" \/><jats:tex-math>\n$k\\geq (1+\\varepsilon) d$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> with probability <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548320000255_inline3.png\" \/><jats:tex-math>\n$1-o(1)$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> over the graph instances.<\/jats:p><jats:p>Our algorithm uses <jats:italic>spatial correlation decay<\/jats:italic> to compute numerically estimates of marginals of the Gibbs distribution. Spatial correlation decay has been used in different counting schemes for deterministic counting. So far algorithms have exploited a certain kind of set-to-point correlation decay, e.g. the so-called <jats:italic>Gibbs uniqueness<\/jats:italic>. Here we deviate from this setting and exploit a point-to-point correlation decay. The spatial mixing requirement is that for a pair of vertices the correlation between their corresponding configurations becomes weaker with their distance.<\/jats:p><jats:p>Furthermore, our approach generalizes in that it allows us to compute the Gibbs marginals for small sets of nearby vertices. Also, we establish a connection between the fluctuations of the number of colourings of <jats:italic>G<\/jats:italic>(<jats:italic>n, d\/n<\/jats:italic>) and the fluctuations of the number of short cycles and edges in the graph.<\/jats:p>","DOI":"10.1017\/s0963548320000255","type":"journal-article","created":{"date-parts":[[2020,6,22]],"date-time":"2020-06-22T09:04:33Z","timestamp":1592816673000},"page":"555-586","update-policy":"http:\/\/dx.doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":0,"title":["Deterministic counting of graph colourings using sequences of subgraphs"],"prefix":"10.1017","volume":"29","author":[{"given":"Charilaos","family":"Efthymiou","sequence":"first","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2020,6,22]]},"reference":[{"key":"S0963548320000255_ref26","unstructured":"[26] Yin, Y. and Zhang, C. (2016) Sampling in Potts model on sparse random graphs. In Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques (APPROX\u2013RANDOM), pp. 1\u201322."},{"key":"S0963548320000255_ref25","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132538"},{"key":"S0963548320000255_ref24","doi-asserted-by":"crossref","unstructured":"[24] Wainright, M. J. and Jordan, M. (2008) Graphical models, exponential families and variational inference. In Found. Trends Mach. Learn. 1 (1\u20132).","DOI":"10.1561\/9781601981851"},{"key":"S0963548320000255_ref23","doi-asserted-by":"publisher","DOI":"10.1063\/1.533196"},{"key":"S0963548320000255_ref22","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.40"},{"key":"S0963548320000255_ref21","doi-asserted-by":"publisher","DOI":"10.1007\/s10955-014-0947-5"},{"key":"S0963548320000255_ref20","doi-asserted-by":"crossref","first-page":"363","DOI":"10.1002\/rsa.3240050209","article-title":"Almost all regular graphs are Hamiltonian","volume":"5","author":"Robinson","year":"1994","journal-title":"Random Struct. Algorithms"},{"key":"S0963548320000255_ref18","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20276"},{"key":"S0963548320000255_ref15","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780198570837.001.0001"},{"key":"S0963548320000255_ref13","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(86)90174-X"},{"key":"S0963548320000255_ref12","unstructured":"[12] Jerrum, M. and Sinclair, A. (1996) The Markov chain Monte Carlo method: an approach to approximate counting and integration. In Approximation Algorithms for NP-hard problems ( Hochbaum, D. S. , ed.), PWS."},{"key":"S0963548320000255_ref11","first-page":"93","article-title":"Approximate counting, uniform generation and rapidly mixing Markov chains","volume":"82","author":"Jerrum","year":"1986","journal-title":"Inform. Comput."},{"key":"S0963548320000255_ref10","doi-asserted-by":"crossref","first-page":"369","DOI":"10.1017\/S0963548300001735","article-title":"Random regular graphs: asymptotic distributions and contiguity","volume":"4","author":"Janson","year":"1995","journal-title":"Combin. Probab. Comput."},{"key":"S0963548320000255_ref9","doi-asserted-by":"crossref","unstructured":"[9] Efthymiou, C. , Hayes, T. , \u0160tefankovi\u010d, D. and Vigoda, E. (2018) Sampling random colorings of sparse random graphs. In 29th Annual ACM\u2013SIAM Symposium on Discrete Algorithms (SODA \u201918), pp. 1759\u20131771.10.1137\/1.9781611975031.115","DOI":"10.1137\/1.9781611975031.115"},{"key":"S0963548320000255_ref8","doi-asserted-by":"crossref","first-page":"2087","DOI":"10.1137\/140977643","article-title":"A simple algorithm for sampling colorings of G(n,d\/n) up to the Gibbs uniqueness threshold","volume":"45","author":"Efthymiou","year":"2016","journal-title":"SIAM J. Comput."},{"key":"S0963548320000255_ref6","doi-asserted-by":"crossref","first-page":"341","DOI":"10.1007\/s00493-016-3394-x","article-title":"Local convergence of random graph colorings","volume":"38","author":"Coja-Oghlan","year":"2018","journal-title":"Combinatorica"},{"key":"S0963548320000255_ref4","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548316000390"},{"key":"S0963548320000255_ref3","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20236"},{"key":"S0963548320000255_ref2","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0068322"},{"key":"S0963548320000255_ref19","doi-asserted-by":"publisher","DOI":"10.1007\/s00440-012-0421-8"},{"key":"S0963548320000255_ref14","unstructured":"[14] Krzakala, F. , Montanari, A. , Ricci-Tersenghi, F. , Semerjianc, G. and Zdeborova, L. (2007) Gibbs states and the set of solutions of random constraint satisfaction problems. Proc. Nat. Acad. Sci. 104 10318\u201310323."},{"key":"S0963548320000255_ref7","unstructured":"[7] Efthymiou, C. (2015) Reconstruction\/non-reconstruction thresholds for colourings of general Galton\u2013Watson trees. In Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques (APPROX\u2013RANDOM), pp. 756\u2013774."},{"key":"S0963548320000255_ref1","doi-asserted-by":"crossref","unstructured":"[1] Achlioptas, D. and Coja-Oghlan, A. (2008) Algorithmic barriers from phase transitions. In 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 793\u2013802.","DOI":"10.1109\/FOCS.2008.11"},{"key":"S0963548320000255_ref17","unstructured":"[17] Montanari, A. and Shah, D. (2007) Counting good truth assignments of random k-SAT formulae. In 18th Annual ACM\u2013SIAM Symposium on Discrete Algorithms (SODA \u201907), pp. 1255\u20131264."},{"key":"S0963548320000255_ref5","doi-asserted-by":"publisher","DOI":"10.1007\/s00220-015-2464-z"},{"key":"S0963548320000255_ref16","doi-asserted-by":"crossref","first-page":"812","DOI":"10.1126\/science.1073287","article-title":"Analytic and algorithmic solution of random satisfiability problems","volume":"297","author":"M\u00e9zard","year":"2002","journal-title":"Science"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548320000255","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,10,13]],"date-time":"2020-10-13T13:36:23Z","timestamp":1602596183000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548320000255\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,22]]},"references-count":26,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2020,7]]}},"alternative-id":["S0963548320000255"],"URL":"https:\/\/doi.org\/10.1017\/s0963548320000255","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,6,22]]},"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"}}]}}