Hostname: page-component-78c5997874-fbnjt Total loading time: 0 Render date: 2024-11-17T06:15:22.105Z Has data issue: false hasContentIssue false
  • English
  • Français

On the Number of Solutions in Random Graph k-Colouring

Part of: Graph theory

Published online by Cambridge University Press:  21 May 2018

FELICIA RASSMANN
FELICIA RASSMANN*
Affiliation:
Institute of Mathematics, Goethe University, 10 Robert-Mayer-Straße, Frankfurt 60325, Germany (e-mail: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

Let k ⩾ 3 be a fixed integer. We exactly determine the asymptotic distribution of ln Zk(G(n, m)), where Zk(G(n, m)) is the number of k-colourings of the random graph G(n, m). 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 G(n, m). Our result holds for a wide range of average degrees, and for k exceeding a certain constant k0 it covers all average degrees up to the so-called condensation phase transition.

MSC classification

Primary: 05C80: Random graphs
Secondary: 05C15: Coloring of graphs and hypergraphs
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 28 , Issue 1 , January 2019 , pp. 130 - 158
Copyright
Copyright © Cambridge University Press 2018 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Footnotes

†

The research leading to these results has received funding from the European Research Council under the European Union's Seventh Framework Programme (FP/2007-2013) / ERC Grant Agreement no. 278857–PTCC.

References

[1] Achlioptas, D. and Coja-Oghlan, A. (2008) Algorithmic barriers from phase transitions. In FOCS '08: IEEE 49th Annual IEEE Symposium on Foundations of Computer Science, IEEE, pp. 793–802.Google Scholar
[2] Achlioptas, D. and Friedgut, E. (1999) A sharp threshold for k-colorability. Random Struct. Alg. 14 63–70.Google Scholar
[3] Achlioptas, D. and Naor, A. (2005) The two possible values of the chromatic number of a random graph. Ann. of Math. 162 1333–1349.Google Scholar
[4] Alon, N. and Krivelevich, M. (1997) The concentration of the chromatic number of random graphs. Combinatorica 17 303–313.Google Scholar
[5] Banks, J., Moore, C., Neeman, J. and Netrapalli, P. (2016) Information-theoretic thresholds for community detection in sparse networks. In COLT: 29th Conference on Learning Theory, MLR Press, pp. 383–416.Google Scholar
[6] Bapst, V., Coja-Oghlan, A. and Efthymiou, C. (2017) Planting colourings silently. Combin. Probab. Comput. 26 338–366.Google Scholar
[7] Bapst, V., Coja-Oghlan, A., Hetterich, S., Raßmann, F. and Vilenchik, D. (2016) The condensation phase transition in random graph coloring. Commun. Math. Phys. 341 543–606.Google Scholar
[8] Bapst, V., Coja-Oghlan, A. and Rassmann, F. (2016) A positive temperature phase transition in random hypergraph 2-colouring. Ann. Appl. Probab. 26 1362–1406.Google Scholar
[9] Bollobás, B. (1988) The chromatic number of random graphs. Combinatorica 8 49–55.Google Scholar
[10] Bollobás, B. (2001) Random Graphs, second edition, Cambridge University Press.Google Scholar
[11] Coja-Oghlan, A. (2013) Upper-bounding the k-colorability threshold by counting covers. Electron. J. Combin. 20 P32.Google Scholar
[12] Coja-Oghlan, A., Efthymiou, C. and Hetterich, S. (2016) On the chromatic number of random regular graphs. J. Combin. Theory Ser. B 116 367–439.Google Scholar
[13] Coja-Oghlan, A. and Vilenchik, D. (2013) Chasing the k-colorability threshold. In FOCS: IEEE 54th Annual Symposium on Foundations of Computer Science, IEEE, pp. 380–389. A full version is available as arXiv:1304.1063.Google Scholar
[14] Coja-Oghlan, A. and Wormald, N. The number of satisfying assignments of random regular k-SAT formulas. arXiv:1611.03236Google Scholar
[15] Erdős, P. and Rényi, A. (1960) On the evolution of random graphs. Magayar Tud. Akad. Mat. Kutato Int. Kozl. 5 17–61.Google Scholar
[16] Frieze, A. and Karónski, M. (2015) Introduction to Random Graphs, Cambridge University Press.Google Scholar
[17] Janson, S. (1995) Random regular graphs: Asymptotic distributions and contiguity. Combin. Probab. Comput. 4 369–405.Google Scholar
[18] Kemkes, G., Perez-Gimenez, X. and Wormald, N. (2010) On the chromatic number of random d-regular graphs. Adv. Math. 223 300–328.Google Scholar
[19] Krzakala, F., Montanari, A., Ricci-Tersenghi, F., Semerjian, G. and Zdeborova, L. (2007) Gibbs states and the set of solutions of random constraint satisfaction problems. Proc. Natl Acad. Sci. 104 10318–10323.Google Scholar
[20] Łuczak, T. (1991) A note on the sharp concentration of the chromatic number of random graphs. Combinatorica 11 295–297.Google Scholar
[21] Łuczak, T. (1991) The chromatic number of random graphs. Combinatorica 11 45–54.Google Scholar
[22] Matula, D. (1987) Expose-and-merge exploration and the chromatic number of a random graph. Combinatorica 7 275–284.Google Scholar
[23] Molloy, M. (2012) The freezing threshold for k-colourings of a random graph. In STOC: 44th Symposium on Theory of Computing, ACM, pp. 921–930.Google Scholar
[24] Montanari, A., Restrepo, R. and Tetali, P. (2011) Reconstruction and clustering in random constraint satisfaction problems. SIAM J. Discrete Math. 25 771–808.Google Scholar
[25] Moore, C. (2016) The phase transition in random regular exact cover. Ann. Inst. Henri Poincaré 3 349–362.Google Scholar
[26] Rassmann, F. (2017) The Electronic Journal of Combinatorics 24 (3) #P3.11.Google Scholar
[27] Robinson, R. and Wormald, N. (1992) Almost all cubic graphs are Hamiltonian. Random Struct. Alg. 3 117–125.Google Scholar
[28] Robinson, R. and Wormald, N. (1994) Almost all regular graphs are Hamiltonian. Random Struct. Alg. 5 363–374.Google Scholar
[29] Shamir, E. and Spencer, J. (1987) Sharp concentration of the chromatic number of random graphs G(n, p). Combinatorica 7 121–129.Google Scholar
[30] Wormald, N. (1999) Models of random regular graphs. In Surveys in Combinatorics, Vol. 267 of London Mathematical Society Lecture Note Series, Cambridge University Press, pp. 239–298.Google Scholar