Name
Abstract | ||
|---|---|---|
We study the effect of boundary conditions on the relaxation time of the Glauber dynamics for the hardcore lattice gas model on the n-vertex regular b-ary tree of height h. 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 h → ∞) 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 b/b where λ = ω(1 + ω)b 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 τ = O (n1+ob(1)) for any ω ≤ ln b/b. In the reconstruction region, for all boundary conditions, we prove τ = O (n1+δ+ob(1)) for ω = (1 + ω) ln b/b, for every δ 0. In contrast, we construct a boundary condition, for which the Glauber dynamics slows down in the reconstruction region, namely τ = Ω (n1+δ-ob(1)) for ω = (1 + δ) ln b/b, 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. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1137/120885498 | Clinical Orthopaedics and Related Research |
Keywords | DocType | Volume |
boundary condition,non-reconstruction region,reconstruction study,glauber dynamic,hardcore lattice gas model,phase transition,reconstruction threshold,typical boundary,hard-core model,reconstruction region,regular tree,independent set,relaxation time,lower bound,state space,distributed computing,randomized algorithms,leader election | Journal | 28 |
Issue | ISSN | ISBN |
2 | 0895-4801 | 978-1-61197-251-1 |
Citations | PageRank | References |
2 | 0.40 | 21 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ricardo Restrepo | 1 | 2 | 0.74 |
| Daniel Stefankovic | 2 | 243 | 28.65 |
| Juan C. Vera | 3 | 50 | 7.98 |
| Eric Vigoda | 4 | 747 | 76.55 |
| Linji Yang | 5 | 58 | 5.17 |