Reconstruction/non-reconstruction thresholds for colourings of general Galton-Watson trees
From MaRDI portal
(Redirected from Publication:5351933)
Coloring of graphs and hypergraphs (05C15) Random graphs (graph-theoretic aspects) (05C80) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)
Abstract: The broadcasting models on trees arise in many contexts such as discrete mathematics, biology statistical physics and cs. In this work, we consider the colouring model. A basic question here is whether the root's assignment affects the distribution of the colourings at the vertices at distance h from the root. This is the so-called "reconstruction problem". For a d-ary tree it is well known that d/ln (d) is the reconstruction threshold. That is, for k=(1+eps)d/ln(d) we have non-reconstruction while for k=(1-eps)d/ln(d) we have. Here, we consider the largely unstudied case where the underlying tree is chosen according to a predefined distribution. In particular, our focus is on the well-known Galton-Watson trees. This model arises naturally in many contexts, e.g. the theory of spin-glasses and its applications on random Constraint Satisfaction Problems (rCSP). The aforementioned study 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).
Recommendations
Cited in
(8)- Phase transitions in discrete structures
- Random instances of problems in NP -- algorithms and statistical physics
- scientific article; zbMATH DE number 2046068 (Why is no real title available?)
- Deterministic counting of graph colourings using sequences of subgraphs
- Non-linear log-Sobolev inequalities for the Potts semigroup and applications to reconstruction problems
- Broadcasting‐induced colorings of preferential attachment trees
- Local convergence of random graph colorings
- Reconstruction of random colourings
This page was built for publication: Reconstruction/non-reconstruction thresholds for colourings of general Galton-Watson trees
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5351933)
