Random directed trees and forest – drainage networks with dependence. (English) Zbl 1185.05124

Athreya, Siva R.; Roy, Rahul; Sarkar, Anish

Electron. J. Probab. 13, 2160-2189 (2008).

Summary: Consider the d-dimensional lattice 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 degree (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 greater than or equal to 4. In addition, for any dimension, we show that there is no bi-infinite path in the tree.

MSC:

05C80	Random graphs (graph-theoretic aspects)
05C81	Random walks on graphs
60K35	Interacting random processes; statistical mechanics type models; percolation theory

Keywords:

random graph; random oriented trees; random walk