Reconstruction/Non-reconstruction Thresholds for Colourings of General Galton-Watson Trees
Reconstruction/Non-reconstruction Thresholds for Colourings of General Galton-Watson Trees
复制标题
一般高尔顿-沃森树着色的重建/非重建阈值
DOI：
--
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Charilaos Efthymiou
中科院分区：
文献类型：
--
作者：
Charilaos Efthymiou
树上的广播模型产生于离散数学、生物学、统计物理和计算机科学等诸多领域。在这项工作中，我们考虑了着色模型。这里的一个基本问题是，根的赋值是否会影响距离根h的顶点的着色分布。这就是所谓的“重建问题”。对于d-ary树，众所周知，d/ln(D)是重建阈值。也就是说，对于k=(1+Eps)d/ln(D)，我们有非重构，而对于k=(1-Eps)d/ln(D)，我们有。
这里，我们考虑一种很大程度上未被研究的情况，即根据预定义的分布选择基础树。特别是，我们的重点是著名的Galton-Watson树。这个模型在许多背景下自然产生，例如自旋玻璃理论及其在随机约束满足问题(RCSP)上的应用。前述研究集中于子代分布为B(n，d/n)的Galton-Watson树，即参数为n和d/n的二叉树，其中d是固定的。这里我们考虑这个问题的一个更广泛的版本，因为我们假设一般的子孙分布，其中包括B(n，d/n)作为特例。
我们的方法将(非)重构的相应界限与子代分布的某些浓度属性联系起来。这允许导出非常广泛的子代分布家族的重建阈值，其中包括B(n，d/n)。一个非常有趣的推论是，对于具有预期子代d的分布，我们在比B(n，d/n)中更弱的浓度条件下得到重建阈值d/ln(D)。
此外，我们对子代为B(n，d/n)的Galton-Watson的随机染色的重建门限也包含了G(n，d/n)的随机染色的重建门限。
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).
随机图着色的局部收敛
影响因子：
1.1
作者：
A. Coja-Oghlan;C. Efthymiou;N. Jafaari
通讯作者：
N. Jafaari