Document Open Access Logo

On a Connectivity Threshold for Colorings of Random Graphs and Hypergraphs

Authors Michael Anastos, Alan Frieze

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2019.36.pdf
  • Filesize: 0.49 MB
  • 10 pages

Document Identifiers

Author Details

Michael Anastos
  • Carnegie Mellon University, Pittsburgh PA 15213, USA
Alan Frieze
  • Carnegie Mellon University, Pittsburgh PA 15213, USA

Funding

  • Frieze, Alan: Research supported in part by NSF grant DMS1661063.

Cite AsGet BibTex

Michael Anastos and Alan Frieze. On a Connectivity Threshold for Colorings of Random Graphs and Hypergraphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 36:1-36:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2019.36

Abstract

Let Omega_q=Omega_q(H) denote the set of proper [q]-colorings of the hypergraph H. Let Gamma_q be the graph with vertex set Omega_q where two vertices are adjacent iff the corresponding colorings differ in exactly one vertex. We show that if H=H_{n,m;k}, k >= 2, the random k-uniform hypergraph with V=[n] and m=dn/k hyperedges then w.h.p. Gamma_q is connected if d is sufficiently large and q >~ (d/log d)^{1/(k-1)}. This is optimal to the first order in d. Furthermore, with a few more colors, we find that the diameter of Gamma_q is O(n) w.h.p, where the hidden constant depends on d. So, with this choice of d,q, the natural Glauber Dynamics Markov Chain on Omega_q is ergodic w.h.p.

Subject Classification

ACM Subject Classification
  • Theory of computation
Keywords
  • Random Graphs
  • Colorings
  • Ergodicity

Metrics

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

References

  1. D. Achlioptas, A. Coja-Oghlan, and F. Ricci-Tersenghi. On the solution-space geometry of random constraint satisfaction problems. Random Structures and Algorithms, 38:251-268, 2010. Google Scholar
  2. P. Ayre, A. Coja-Oghlan, and C. Greenhill. Hypergraph coloring up to condensation. arxiv:1508.01841, 2019. URL: http://arxiv.org/abs/1508.01841.
  3. P. Ayre and C. Greenhill. Rigid colourings of hypergraphs and contiguity. arxiv:1812.03195, 2019. URL: http://arxiv.org/abs/1812.03195.
  4. V. Bapst, A. Coja-Oghlan, S. Hetterich, F. Rassmann, and D. Vilenchik. The condensation phase transition in random graph coloring. Communications in Mathematical Physics, 341:543-606, 2016. Google Scholar
  5. N. Bousquet and G. Perarnau. Fast recoloring of sparse graphs. European Journal of Combinatorics, 52:1-11, 2016. Google Scholar
  6. C. Efthymiou, T. Hayes, D. Štefankovič, and E. Vigoda. Sampling Colorings of Sparse random Graphs. In SODA, 2018. Google Scholar
  7. C. Feghali. Paths between colourings of sparse graphs. European Journal of Combinatorics, 75:169-171, 2019. Google Scholar
  8. A.M. Frieze and M. Karoński. Introduction to Random Graphs. Cambridge University Press, 2015. Google Scholar
  9. M. Gabrié, V. Dani, G. Semerjian, and L. Zdeborová. Phase transitions in the q-coloring of random hypergraphs. Journal of Physics A: Mathematical Theory, 50, 2017. Google Scholar
  10. A. Sly J. Ding and N. Sun. Proof of the satisfiability conjecture for large k. arxiv:1411.0650, 2019. URL: http://arxiv.org/abs/1411.0650.
  11. F. Krzaka̧la, A. Montanari, F. Ricci-Tersenghi, G. Semerijian, and L. Zdeborová. Gibbs states and the set of solutions of random constraint satisfaction problems. Proceedings of the National Academy of Sciences, 104:10318-10323, 2007. Google Scholar
  12. Anastos M., A.M. Frieze, and W. Pegden. Constraining the clustering transition for colorings of sparse random graphs. Electronic Journal of Combinatorics, 2018. Google Scholar
  13. and A. Flaxman M. Dyer, A.M. Frieze, and E. Vigoda. Randomly coloring sparse random graphs with fewer colors than the maximum degree. Random Structures and Algorithms, 29:450-465, 2006. Google Scholar
  14. M. Molloy. The freezing threshold for k-colourings of a random graph. In STOC, 2012. Google Scholar
  15. E. Shamir and E. Upfal. Sequential and Distributed Graph Coloring Algorithms with Performance Analysis in Random Graph Spaces. Journal of Algorithms, 5:488-501, 1984. Google Scholar
  16. L. Zdeborová and F. Krzaka̧la. Phase Transitions in the Coloring of Random Graphs. Physics Review E, 76, 2007. 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