DMTCS Proceedings, Discrete Random Walks, DRW'03

Font Size:  Small  Medium  Large

Reconstruction Thresholds on Regular Trees

James B. Martin


We consider the model of broadcasting on a tree, with binary state space, on the infinite rooted tree Tk in which each node has k children. The root of the tree takes a random value 0 or 1, and then each node passes a value independently to each of its children according to a 2x2 transition matrix P. We say that reconstruction is possible if the values at the dth level of the tree contain non-vanishing information about the value at the root as d→∞. Extending a method of Brightwell and Winkler, we obtain new conditions under which reconstruction is impossible, both in the general case and in the special case p11=0. The latter case is closely related to the hard-core model from statistical physics; a corollary of our results is that, for the hard-core model on the (k+1)-regular tree with activity λ=1, the unique simple invariant Gibbs measure is extremal in the set of Gibbs measures, for any k ≥ 2.

Full Text: GZIP Compressed PostScript PostScript PDF original HTML abstract page

Valid XHTML 1.0 Transitional