Nothing Special   »   [go: up one dir, main page]
Document Open Access Logo

Local Convergence of Random Graph Colorings

Authors Amin Coja-Oghlan, Charilaos Efthymiou, Nor Jaafari

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2015.726.pdf
  • Filesize: 481 kB
  • 12 pages

Document Identifiers

Author Details

Amin Coja-Oghlan
Charilaos Efthymiou
Nor Jaafari

Cite AsGet BibTex

Amin Coja-Oghlan, Charilaos Efthymiou, and Nor Jaafari. Local Convergence of Random Graph Colorings. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 40, pp. 726-737, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2015.726

Abstract

Let G=G(n,m) be a random graph whose average degree d=2m/n is below the k-colorability threshold. If we sample a k-coloring Sigma of G uniformly at random, what can we say about the correlations between the colors assigned to vertices that are far apart? According to a prediction from statistical physics, for average degrees below the so-called condensation threshold d_c, the colors assigned to far away vertices are asymptotically independent [Krzakala et al: PNAS 2007]. We prove this conjecture for k exceeding a certain constant k_0. More generally, we determine the joint distribution of the k-colorings that Sigma induces locally on the bounded-depth neighborhoods of a fixed number of vertices.
Keywords
  • Random graph
  • Galton-Watson tree
  • phase transitions
  • graph coloring
  • Gibbs distribution
  • convergence

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Dimitris Achlioptas and Amin Coja-Oghlan. Algorithmic barriers from phase transitions. In Foundations of Computer Science, 2008. FOCS'08. IEEE 49th Annual IEEE Symposium on, pages 793-802. IEEE, 2008. Google Scholar
  2. Dimitris Achlioptas and Ehud Friedgut. A sharp threshold for k-colorability. Random Structures Algorithms, 14(1):63-70, 1999. Google Scholar
  3. Dimitris Achlioptas and Michael Molloy. The analysis of a list-coloring algorithm on a random graph. In Foundations of Computer Science, 1997. Proceedings., 38th Annual Symposium on, pages 204-212. IEEE, 1997. Google Scholar
  4. Dimitris Achlioptas and Assaf Naor. The two possible values of the chromatic number of a random graph. In Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, pages 587-593. ACM, 2004. Google Scholar
  5. Noga Alon and Michael Krivelevich. The concentration of the chromatic number of random graphs. Combinatorica, 17(3):303-313, 1997. Google Scholar
  6. Victor Bapst, Amin Coja-Oghlan, and Charilaos Efthymiou. Planting colourings silently. arXiv preprint arXiv:1411.0610, 2014. Google Scholar
  7. Victor Bapst, Amin Coja-Oghlan, Samuel Hetterich, Felicia Raßmann, and Dan Vilenchik. The condensation phase transition in random graph coloring. arXiv preprint arXiv:1404.5513, 2014. Google Scholar
  8. Nayantara Bhatnagar, Allan Sly, and Prasad Tetali. Decay of correlations for the hardcore model on the d-regular random graph. arXiv preprint arXiv:1405.6160, 2014. Google Scholar
  9. Béla Bollobás. The chromatic number of random graphs. Combinatorica, 8(1):49-55, 1988. Google Scholar
  10. Amin Coja-Oghlan. Upper-bounding the k-colorability threshold by counting covers. arXiv preprint arXiv:1305.0177, 2013. Google Scholar
  11. Amin Coja-Oghlan and Dan Vilenchik. Chasing the k-colorability threshold. In Foundations of Computer Science (FOCS), 2013 IEEE 54th Annual Symposium on, pages 380-389. IEEE, 2013. Google Scholar
  12. Martin Dyer and Alan Frieze. Randomly coloring random graphs. Random Structures & Algorithms, 36(3):251-272, 2010. Google Scholar
  13. Martin Dyer, Alistair Sinclair, Eric Vigoda, and Dror Weitz. Mixing in time and space for lattice spin systems: A combinatorial view. Random Structures & Algorithms, 24(4):461-479, 2004. Google Scholar
  14. Charilaos Efthymiou. MCMC sampling colourings and independent sets of G(n, d/n) near uniqueness threshold. In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 305-316. SIAM, 2014. Google Scholar
  15. Charilaos Efthymiou. Reconstruction/non-reconstruction thresholds for colourings of general Galton-watson trees. arXiv preprint arXiv:1406.3617, 2014. Google Scholar
  16. Charilaos Efthymiou. Switching colouring of G(n, d/n) for sampling up to Gibbs uniqueness threshold. In Algorithms-ESA 2014, pages 371-381. Springer, 2014. Google Scholar
  17. Paul Erdős. Graph theory and probability. canad. J. Math, 11:34G38, 1959. Google Scholar
  18. Paul Erdős and A Rényi. On the evolution of random graphs. Publ. Math. Inst. Hungar. Acad. Sci, 5:17-61, 1960. Google Scholar
  19. Andreas Galanis, Qi Ge, Daniel Štefankovič, Eric Vigoda, and Linji Yang. Improved inapproximability results for counting independent sets in the hard-core model. Random Structures & Algorithms, 45(1):78-110, 2014. Google Scholar
  20. Andreas Galanis, Daniel Štefankovič, and Eric Vigoda. Inapproximability for antiferromagnetic spin systems in the tree non-uniqueness region. In Proceedings of the 46th Annual ACM Symposium on Theory of Computing, pages 823-831. ACM, 2014. Google Scholar
  21. Hans-Otto Georgii. Gibbs measures and phase transitions, volume 9. Walter de Gruyter, 2011. Google Scholar
  22. Antoine Gerschenfeld and Andrea Montanari. Reconstruction for models on random graphs. In Foundations of Computer Science, 2007. FOCS'07. 48th Annual IEEE Symposium on, pages 194-204. IEEE, 2007. Google Scholar
  23. Geoffrey R Grimmett and Colin JH McDiarmid. On colouring random graphs. In Mathematical Proceedings of the Cambridge Philosophical Society, volume 77, pages 313-324. Cambridge Univ Press, 1975. Google Scholar
  24. Michael Krivelevich and Benny Sudakov. Coloring random graphs. Information Processing Letters, 67(2):71-74, 1998. Google Scholar
  25. Florent Krzakała, Andrea Montanari, Federico Ricci-Tersenghi, Guilhem Semerjian, and Lenka Zdeborová. Gibbs states and the set of solutions of random constraint satisfaction problems. Proceedings of the National Academy of Sciences, 104(25):10318-10323, 2007. Google Scholar
  26. Tomasz Łuczak. The chromatic number of random graphs. Combinatorica, 11(1):45-54, 1991. Google Scholar
  27. Tomasz Łuczak. A note on the sharp concentration of the chromatic number of random graphs. Combinatorica, 11(3):295-297, 1991. Google Scholar
  28. Fabio Martinelli, Alistair Sinclair, and Dror Weitz. Fast mixing for independent sets, colorings, and other models on trees. Random Structures & Algorithms, 31(2):134-172, 2007. Google Scholar
  29. David W Matula. Expose-and-merge exploration and the chromatic number of a random graph. Combinatorica, 7(3):275-284, 1987. Google Scholar
  30. Marc Mézard and Andrea Montanari. Information, physics, and computation. Oxford University Press, 2009. Google Scholar
  31. Marc Mézard, Giorgio Parisi, and Riccardo Zecchina. Analytic and algorithmic solution of random satisfiability problems. Science, 297(5582):812-815, 2002. Google Scholar
  32. Michael Molloy. The freezing threshold for k-colourings of a random graph. In Proceedings of the forty-fourth annual ACM symposium on Theory of computing, pages 921-930. ACM, 2012. Google Scholar
  33. Andrea Montanari, Ricardo Restrepo, and Prasad Tetali. Reconstruction and clustering in random constraint satisfaction problems. SIAM Journal on Discrete Mathematics, 25(2):771-808, 2011. Google Scholar
  34. Jaroslav Nešetřil. A combinatorial classic—sparse graphs with high chromatic number. In Erdős Centennial, pages 383-407. Springer, 2013. Google Scholar
  35. Olivier Rivoire, Giulio Biroli, Olivier C Martin, and Marc Mézard. Glass models on bethe lattices. The European Physical Journal B-Condensed Matter and Complex Systems, 37(1):55-78, 2004. Google Scholar
  36. Eli Shamir and Joel Spencer. Sharp concentration of the chromatic number on random graphs G(n,p). Combinatorica, 7(1):121-129, 1987. Google Scholar
  37. Allan Sly. Computational transition at the uniqueness threshold. In Foundations of Computer Science (FOCS), 2010 51st Annual IEEE Symposium on, pages 287-296. IEEE, 2010. Google Scholar
  38. Yitong Yin and Chihao Zhang. Sampling colorings almost uniformly in sparse random graphs. arXiv preprint arXiv:1503.03351, 2015. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact