Document Open Access Logo

Reconstruction/Non-reconstruction Thresholds for Colourings of General Galton-Watson Trees

Author Charilaos Efthymiou

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2015.756.pdf
  • Filesize: 0.5 MB
  • 19 pages

Document Identifiers

Author Details

Charilaos Efthymiou

Cite AsGet BibTex

Charilaos Efthymiou. Reconstruction/Non-reconstruction Thresholds for Colourings of General Galton-Watson Trees. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 40, pp. 756-774, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2015.756

Abstract

The broadcasting models on trees arise in many contexts such as discrete mathematics, biology, information theory, statistical physics and computer science. In this work, we consider the k-colouring model. A basic question here is whether the assignment at the root affects the distribution of the colourings at the vertices at distance h from the root. This is the so-called reconstruction problem. For the case where the underlying tree is d -ary it is well known that d/ln(d) is the reconstruction threshold. That is, for k=(1+epsilon)*d/ln(d) we have non-reconstruction while for k=(1-epsilon)*d/ln(d) we have reconstruction. Here, we consider the largely unstudied case where the underlying tree is chosen according to a predefined distribution. In particular, we consider the well-known Galton-Watson trees. The corresponding model arises naturally in many contexts such as the theory of spin-glasses and its applications on random Constraint Satisfaction Problems (rCSP). The study on rCSP focuses on Galton-Watson trees with offspring distribution B(n,d/n), i.e. the binomial with parameters n and d/n, where d is fixed. Here we consider a broader version of the problem, as we assume general offspring distribution which includes B(n,d/n) as a special case. Our approach relates the corresponding bounds for (non)reconstruction to certain concentration properties of the offspring distribution. This allows to derive reconstruction thresholds for a very wide family of offspring distributions, which includes B(n,d/n). A very interesting corollary is that for distributions with expected offspring d, we get reconstruction threshold d/ln(d) under weaker concentration conditions than what we have in B(n,d/n). Furthermore, our reconstruction threshold for the random colorings of Galton-Watson with offspring B(n,d/n), implies the reconstruction threshold for the random colourings of G(n,d/n).
Keywords
  • Random Colouring
  • Reconstruction Problem
  • Galton-Watson Tree

Metrics

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

References

  1. D. Achlioptas and A. Coja-Oghlan. Algorithmic barriers from phase transitions. In Foundations of Computer Science, 2008. FOCS'08. IEEE 49th Annual IEEE Symposium on, pages 793-802, Oct 2008. Google Scholar
  2. Nayantara Bhatnagar, Allan Sly, and Prasad Tetali. Reconstruction threshold for the hardcore model. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 13th International Workshop, APPROX 2010, and 14th International Workshop, RANDOM 2010, Barcelona, Spain, September 1-3, 2010. Proceedings, pages 434-447, 2010. Google Scholar
  3. Nayantara Bhatnagar, Juan Carlos Vera, Eric Vigoda, and Dror Weitz. Reconstruction for colorings on trees. SIAM J. Discrete Math., 25(2):809-826, 2011. Google Scholar
  4. Christian Borgs, Jennifer T. Chayes, Elchanan Mossel, and Sébastien Roch. The kesten-stigum reconstruction bound is tight for roughly symmetric binary channels. In 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 21-24 October 2006, Berkeley, California, USA, Proceedings, pages 518-530, 2006. Google Scholar
  5. J. T. Chayes, L. Chayes, James P. Sethna, and D. J. Thouless. A mean field spin glass with short-range interactions. Comm. Math. Phys., 106(1):41-89, 1986. Google Scholar
  6. Amin Coja-Oghlan. A better algorithm for random k-sat. SIAM J. Comput., 39(7):2823-2864, 2010. Google Scholar
  7. Amin Coja-Oghlan, Charilaos Efthymiou, and Nor Jaafari. Local convergence of random graph colorings. CoRR, abs/1501.06301, 2015. Google Scholar
  8. Constantinos Daskalakis, Elchanan Mossel, and Sébastien Roch. Optimal phylogenetic reconstruction. In Proceedings of the 38th Annual ACM Symposium on Theory of Computing, Seattle, WA, USA, May 21-23, 2006, pages 159-168, 2006. Google Scholar
  9. Martin E. Dyer, Abraham D. Flaxman, Alan M. Frieze, and Eric Vigoda. Randomly coloring sparse random graphs with fewer colors than the maximum degree. Random Struct. Algorithms, 29(4):450-465, 2006. Google Scholar
  10. Charilaos Efthymiou. A simple algorithm for random colouring G(n, d/n) using (2 + ε)d colours. In Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, Kyoto, Japan, January 17-19, 2012, pages 272-280, 2012. Google Scholar
  11. 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, SODA 2014, Portland, Oregon, USA, January 5-7, 2014, pages 305-316, 2014. Google Scholar
  12. Charilaos Efthymiou. Reconstruction/non-reconstruction thresholds for colourings of general galton-watson trees. CoRR, abs/1406.3617, 2014. Google Scholar
  13. Charilaos Efthymiou. Switching colouring of g(n, d/n) for sampling up to gibbs uniqueness threshold. In Algorithms - ESA 2014 - 22th Annual European Symposium, Wroclaw, Poland, September 8-10, 2014. Proceedings, pages 371-381, 2014. Google Scholar
  14. William Evans, Claire Kenyon, Yuval Peres, and Leonard J. Schulman. Broadcasting on trees and the ising model. Ann. Appl. Probab., 10(2):410-433, 05 2000. Google Scholar
  15. Antoine Gerschenfeld and Andrea Montanari. Reconstruction for models on random graphs. In 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), October 20-23, 2007, Providence, RI, USA, Proceedings, pages 194-204, 2007. Google Scholar
  16. Geoffrey R Grimmett and Colin JH McDiarmid. On colouring random graphs. Mathematical Proceedings of the Cambridge Philosophical Society Mathematical Proceedings of the Cambridge Philosophical Society, 77(02):311-324, 1975. Google Scholar
  17. 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
  18. Marc Mézard, Giorgio Parisi, and Riccardo Zecchina. Analytic and algorithmic solution of random satisfiability problems. Science, 297(5582):812-815, 2002. Google Scholar
  19. Michael Molloy. The freezing threshold for k-colourings of a random graph. In Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, New York, NY, USA, May 19-22, 2012, pages 921-930, 2012. Google Scholar
  20. Andrea Montanari, Ricardo Restrepo, and Prasad Tetali. Reconstruction and clustering in random constraint satisfaction problems. SIAM J. Discrete Math., 25(2):771-808, 2011. Google Scholar
  21. E. Mossel. Phase transitions in phylogeny. Trans. Amer. Math. Soc., 356(6):2379-2404 (electronic), 2004. Google Scholar
  22. E. Mossel and Y. Peres. Information flow on trees. Ann. Appl. Probab., 13(3):817-844, 2003. Google Scholar
  23. Elchanan Mossel. Reconstruction on trees: Beating the second eigenvalue. Ann. Appl. Probab., 11(1):285-300, 02 2001. Google Scholar
  24. Rajeev Motwani and Prabhakar Raghavan. Randomized Algorithms. Cambridge University Press,, 1995. Google Scholar
  25. Guilhem Semerjian. On the freezing of variables in random constraint satisfaction problems. Journal of Statistical Physics, 130(2):251- 293, January 2008. Google Scholar
  26. Allan Sly. Reconstruction of random colourings. Communications in Mathematical Physics, 288(3):943-961, 2009. Google Scholar
  27. Yitong Yin and Chihao Zhang. Sampling colorings almost uniformly in sparse random graphs. CoRR, abs/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