Theoretical Statistics and Mathematics Unit, ISI Delhi

Random directed trees and forest

by Siva Athreya, Rahul Roy and Anish Sarkar

Consider the $d$-dimensional lattice $\mathbb Z^d$ where each vertex is `open'
or `closed' with probability $p$ or $1-p$ respectively. An open
vertex $v$ is connected by an edge to the closest open vertex $
w$ in the $45^\circ$ (downward) light cone generated at $v$.
In case of non-uniqueness of such a vertex $w$, we choose any one
of the closest vertices with equal
probability and independently of the other random mechanisms. It
is shown that this random graph is a tree almost surely for $d=2$
and $3$ and it is an infinite collection of distinct trees for $d
\geq 4$. In addition, for any dimension, we show that there is no
bi-infinite path in the tree.

isid/ms/2008/01 [fulltext]

Click here to return to Preprints Page