A key insight from statistical physics about spin systems on random graphs is the central role played by Gibbs measures on trees. We determine the local weak limit of the hardcore model on random regular graphs asymptotically until just below its condensation threshold, showing that it converges in probability locally in a strong sense to the free boundary condition Gibbs measure on the tree. As a consequence we show that the reconstruction threshold on the random graph, indicative of the onset of point to set spatial correlations, is equal to the reconstruction threshold on the @math -regular tree for which we determine precise asymptotics. We expect that our methods will generalize to a wide range of spin systems for which the second moment method holds.
@cite_19: Consider a Markov chain on an infinite tree T = (V,E) rooted at . In such a chain, once the initial root state ( ) is chosen, each vertex iteratively chooses its state from the one of its parent by an application of a Markov transition rule (and all such applications are independent). Let µj denote the resulting measure for ( ) = j. µj is defined on configurations = ( (x))x2V 2 A V , where A is some finite set. Let µ n denote the restriction of µ to the sigma-algebra generated by the variables (x) where x is at distance exactly n from . Letting n = maxi,j2A dTV (µ n ,µ n ), where dTV denotes total variation distance, we say that the reconstruction problem is solvable if liminfn!1 n > 0. Reconstruction solvability roughly means that the n’th level of the tree contains a non-vanishing amount of information on the root of the tree, as n ! 1. In this paper we study the problem of robust reconstruction. Let be a non degenerate distribution on A and > 0. Let be chosen according to µ n and 0 be obtained from by letting for each node independently (v) = 0 (v) with probability 1 and 0 (v) to be an independent sample from otherwise. We denote by µ n [, ] the resulting measure on 0 . The measure µ n [, ] is a perturbation of the measure µ n . Letting n(, ) = maxi,j2A dTV (µ n [, ],µ n [, ]), we say that the reconstruction problem is -robust-solvable if liminfn!1 n(, ) > 0 for all 0 1, where 2(M) is the second largest eigenvalue of M (in absolute value), then for all non-degenerate , the reconstruction problem is -robust-solvable. We prove a converse and show that the reconstruction problem is not -robust-solvable if B| 2(M)| 2 < 1. This proves a conjecture by the second author and Peres. We also consider other models of noise and general trees.
@cite_27: Consider k-colorings of the complete tree of depth l and branching factor Δ. If we fix the coloring of the leaves, for what range of k is the root uniformly distributed over all k colors (in the limit l→∞)? This corresponds to the threshold for uniqueness of the infinite-volume Gibbs measure. It is straightforward to show the existence of colorings of the leaves which “freeze” the entire tree when k≤Δ+1. For k≥Δ+2, Jonasson proved the root is “unbiased” for any fixed coloring of the leaves, and thus the Gibbs measure is unique. What happens for a typical coloring of the leaves? When the leaves have a nonvanishing influence on the root in expectation, over random colorings of the leaves, reconstruction is said to hold. Nonreconstruction is equivalent to extremality of the free-boundary Gibbs measure. When k 1 and k=CΔ lnΔ, nonreconstruction holds; i.e., the Gibbs measure is extr...
@cite_34: Reconstruction problems have been studied in a number of contexts including biology, information theory and statistical physics. We consider the reconstruction problem for random k-colourings on the Δ-ary tree for large k. [2] showed non-reconstruction when ( k k - o(k k) ) . We tighten this result and show non-reconstruction when ( k[ k + k + 1 - 2 -o(1)] ) , which is very close to the best known bound establishing reconstruction which is ( k[ k + k + 1+o(1)] ).
In both the coloring model and the hardcore model the reconstruction threshold is far from the Kesten-Stigum bound for large @math . In the coloring model close to optimal bounds on the reconstruction threshold @cite_27 @cite_34 were obtained by first showing that, when @math is small, the information on the root is sufficiently small. Then a quantitative version of @cite_19 establishes that the information on the root converges to 0 exponentially quickly. In this work, we show that the hardcore model behaves similarly.