摘要翻译：
考虑连接到图顶点的随机变量的集合。重建问题要求估计其中一个给定“遥远”的观测。当它们的联合概率分布是关于树的马尔可夫分布时，可以得到几个理论结果（和简单算法）。本文考虑随机图序列局部收敛于树的情形。特别地，我们给出了树与图重构问题重合的一个充分条件。我们将此条件应用于随机图的着色。进一步，我们在这类图上刻画了伊辛模型的行为，既有吸引相互作用，也有随机相互作用（分别是“铁磁”和“自旋玻璃”）。
---
英文标题：
《Reconstruction for models on random graphs》
---
作者：
Antoine Gerschenfeld and Andrea Montanari
---
最新提交年份：
2007
---
分类信息：

一级分类：Mathematics        数学
二级分类：Probability        概率
分类描述：Theory and applications of probability and stochastic processes: e.g. central limit theorems, large deviations, stochastic differential equations, models from statistical mechanics, queuing theory
概率论与随机过程的理论与应用：例如中心极限定理，大偏差，随机微分方程，统计力学模型，排队论
--
一级分类：Physics        物理学
二级分类：Statistical Mechanics        统计力学
分类描述：Phase transitions, thermodynamics, field theory, non-equilibrium phenomena, renormalization group and scaling, integrable models, turbulence
相变，热力学，场论，非平衡现象，重整化群和标度，可积模型，湍流
--
一级分类：Mathematics        数学
二级分类：Combinatorics        组合学
分类描述：Discrete mathematics, graph theory, enumeration, combinatorial optimization, Ramsey theory, combinatorial game theory
离散数学，图论，计数，组合优化，拉姆齐理论，组合对策论
--

---
英文摘要：
  Consider a collection of random variables attached to the vertices of a graph. The reconstruction problem requires to estimate one of them given `far away' observations. Several theoretical results (and simple algorithms) are available when their joint probability distribution is Markov with respect to a tree. In this paper we consider the case of sequences of random graphs that converge locally to trees. In particular, we develop a sufficient condition for the tree and graph reconstruction problem to coincide. We apply such condition to colorings of random graphs.   Further, we characterize the behavior of Ising models on such graphs, both with attractive and random interactions (respectively, `ferromagnetic' and `spin glass').
---
PDF链接：
https://arxiv.org/pdf/704.3293