Efthymiou, Charilaos
Reconstruction/Nonreconstruction Thresholds for Colourings of General GaltonWatson Trees
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 kcolouring 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 socalled 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 nonreconstruction while for k=(1epsilon)*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 wellknown GaltonWatson trees. The corresponding model arises naturally in many contexts such as
the theory of spinglasses and its applications on random Constraint Satisfaction Problems (rCSP). The study on rCSP focuses on GaltonWatson 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 GaltonWatson 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/Nonreconstruction Thresholds for Colourings of General GaltonWatson Trees}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)},
pages = {756774},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897897},
ISSN = {18688969},
year = {2015},
volume = {40},
editor = {Naveen Garg and Klaus Jansen and Anup Rao and Jos{\'e} D. P. Rolim},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2015/5334},
URN = {urn:nbn:de:0030drops53346},
doi = {10.4230/LIPIcs.APPROXRANDOM.2015.756},
annote = {Keywords: Random Colouring, Reconstruction Problem, GaltonWatson Tree}
}
13.08.2015
Keywords: 

Random Colouring, Reconstruction Problem, GaltonWatson Tree 
Seminar: 

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)

Issue date: 

2015 
Date of publication: 

13.08.2015 