License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2015.756
URN: urn:nbn:de:0030-drops-53346
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/5334/
Go to the corresponding LIPIcs Volume Portal

Efthymiou, Charilaos

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

pdf-format:
44.pdf (0.5 MB)

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).


BibTeX - Entry

@InProceedings{efthymiou:LIPIcs:2015:5334,
  author =	{Charilaos Efthymiou},
  title =	{{Reconstruction/Non-reconstruction Thresholds for Colourings of General Galton-Watson Trees}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)},
  pages =	{756--774},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-89-7},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{40},
  editor =	{Naveen Garg and Klaus Jansen and Anup Rao and Jos{\'e} D. P. Rolim},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2015/5334},
  URN =		{urn:nbn:de:0030-drops-53346},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2015.756},
  annote =	{Keywords: Random Colouring, Reconstruction Problem, Galton-Watson Tree}
}

Keywords: Random Colouring, Reconstruction Problem, Galton-Watson Tree
Collection: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)
Issue Date: 2015
Date of publication: 13.08.2015

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI