Reconstruction on Regular Trees and the Hard-Core Model
Phase Transitions in Computation and Reconstruction
March 07, 2005 02:00 PM to 02:20 PM
Speakers:
|
 |
Summary: |
The talk is about the model of broadcasting on a tree, with binary state
space, on the rooted tree $T_k$ 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 $d$th level of the tree contain non-vanishing information about the
value at the root as $d\to\infty$. I'll describe conditions under which
reconstruction is impossible, both in the general case and in the
special case $p_{11}=0$. The latter case is closely related to the "hard-core
model" from statistical physics; a corollary of the results is that, for
the hard-core model on the $(k+1)$-regular tree with activity
$\lambda=1$, the unique simple invariant Gibbs measure is extremal in the set of
Gibbs measures, for any $k$. |
Keywords: |
Phase Transition;Computation;Reconstruction |
|
|
