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

@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}
}