Phase transition for Glauber dynamics for independent sets on regular trees
Phase transition for Glauber dynamics for independent sets on regular trees
复制标题
常规树上独立集的 Glauber 动力学相变
DOI：
10.1137/120885498
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
Linji Yang
中科院分区：
文献类型：
--
作者：
R. Restrepo;Daniel Stefankovic;Juan C. Vera;Eric Vigoda;Linji Yang
研究了高<i>h</i><i>的n</i>点正则<i>B</i>叉树上硬核格子气模型的Glauber动力学的弛豫时间与边界条件的关系。核心模型定义在由树上的活动（或逸度）λ加权的独立集上。重建研究“典型”边界条件的影响，即，在根上对叶子进行固定赋值。重建发生时的阈值（以及典型边界影响极限<i>h</i>→ ∞中的根）最近引起了相当大的兴趣，因为它似乎与局部树状图上某些局部算法的效率有关。重建阈值出现在ω λ ln<i>B/B</i>处，其中λ = ω（1 + ω）<sup><i>B</i></sup>是模型的方便的重新参数化。
证明了对于所有边界条件，非重构区的弛豫时间τ是快的，即对任意ω ≤ ln<i>B/B，</i>τ =<i>O</i>（<i>n1</i><sup>+<i>ob</i>（1）</sup>）.在重构区域，对于所有的边界条件，我们证明了τ =<i>O</i>（<i>n1</i><sup>+Δ+ob（1）</sup>），其中ω =（1 + ω）ln<i>B/B</i>，对任何Δ > 0.与此相反，我们构造了一个边界条件，使得Glauber动力学在重构区域内变慢，即τ = Ω（<i>n1</i><sup>+Δ-ob（1）</sup>），其中ω =（1 + Δ）ln<i>B/B</i>，对每个Δ > 0.有趣的部分，我们的证明是这个下界的结果，它使用了一个通用的技术，转换算法，以证明重建到一个集的状态空间中的Glauber动力学与不良的电导。
We study the effect of boundary conditions on the relaxation time of the Glauber dynamics for the hardcore lattice gas model on the <i>n</i>-vertex regular <i>b</i>-ary tree of height <i>h</i>. The hard-core model is defined on independent sets weighted by an activity (or fugacity) λ on trees. Reconstruction studies the effect of a 'typical' boundary condition, i.e., fixed assignment to the leaves, on the root. The threshold for when reconstruction occurs (and a typical boundary influences the root in the limit <i>h</i> → ∞) has been of considerable recent interest since it appears to be connected to the efficiency of certain local algorithms on locally tree-like graphs. The reconstruction threshold occurs at ω ≈ ln <i>b/b</i> where λ = ω(1 + ω)<sup><i>b</i></sup> is a convenient re-parameterization of the model.
We prove that for all boundary conditions, the relaxation time τ in the non-reconstruction region is fast, namely τ = <i>O</i> (<i>n</i><sup>1+<i>ob</i>(1)</sup>) for any ω ≤ ln <i>b/b</i>. In the reconstruction region, for all boundary conditions, we prove τ = <i>O</i> (<i>n</i><sup>1+Δ+ob(1)</sup>) for ω = (1 + ω) ln <i>b/b</i>, for every Δ > 0. In contrast, we construct a boundary condition, for which the Glauber dynamics slows down in the reconstruction region, namely τ = Ω (<i>n</i><sup>1+Δ-ob(1)</sup>) for ω = (1 + Δ) ln <i>b/b</i>, for every Δ > 0. The interesting part of our proof is this lower bound result, which uses a general technique that transforms an algorithm to prove reconstruction into a set in the state space of the Glauber dynamics with poor conductance.