On the number of solutions in random graph k-colouring

2016/09/14 by Felicia Raßmann, Rassmann, Felicia
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #Stochastic processes and statistical mechanics

paper · pdf · doi:10.48550/arxiv.1609.04191

openalex publication_date 2016/09/14 · openalex created_date 2016/09/23 · openalex updated_date 2026/07/28

Abstract

Let k ≥ 3 be a fixed integer. We exactly determine the asymptotic distribution of ln Z_k(G(n,m)), where Z_k(G(n,m)) is the number of k-colourings of the random graph G(n,m). A crucial observation to this aim is that the fluctuations in the number of colourings can be attributed to the fluctuations in the number of small cycles in G(n,m). Our result holds for a wide range of average degrees, and for k exceeding a certain constant k₀ it covers all average degrees up to the so-called "condensation phase transition".

Citations

• Non-Reconstructability in the Stochastic Block Model

Related

• On the number of solutions in random hypergraph 2-colouring
• Colouring random subgraphs
• Clique colouring of binomial random graphs
• Critical Exponent for the Acyclic Chromatic Number of Random Graphs
• Colouring random graphs: Tame colourings