Wednesday 1 August 2007

pr.probability - Decimating the infinite grid graph

Let $G$ be the graph whose nodes are the points of
$mathbb{Z}^d$ in the nonnegative orthant (i.e., all
coordinates are $ge 0$), with edges connecting each
pair of points separated by unit distance.
So the degree of each node not on the boundary is $2d$.
Now delete each node with probability $delta$,
except always retain the origin $o=(0,0,ldots,0)$.
Let $G_delta$ be the component connected to $o$.




Question 1. Does $G_delta$ contain a simple path
from the origin of infinite length?




The length of a path is its number of edges.
A simple path does not cross itself.
For $d{=}1$, the answer is 'No' for any $delta > 0$,
because eventually the run of nodes connected to $o$ will
be broken. So, almost surely every path is of finite length.
The situation is less clear to me for $d ge 2$.
Some experimentation tentatively suggests that for $d{=}2$ and $delta=frac{1}{2}$, the answer is again 'No.'



When the answer to Question 1 is 'No,'
let $r(d,delta)$ be the radius of $G_delta$, defined to be the expected length of the longest of the shortest paths
from $o$ within $G_delta$.




Question 2. What is $r(d,delta)$?




For $d{=}1$, I believe the radius is
$$sum_{k=1}^{infty} k (1-delta)^k delta = (1-delta)/delta ;.$$
For example, $r(1,frac{1}{4})=3$.
The $d{=}2$ example below shows a shortest path of length 18 connecting
$(0,0)$ to $(10,4)$. (Yellow=deleted nodes, green=component connected to origin,
blue=undeleted but disconnected from origin.)
I produced this example with $delta=0.55$.




alt text



I suspect these questions have been addressed in the literature
on random graphs, with which I am not so familiar.
Any references, reformulations, proof ideas, or partial solutions ($d{=}2$ and $d{=}3$
are of special interest to me), would be appreciated.
Thanks!



Edit. Thanks for all the references. From what I have learned so far, the model I defined is known as site percolation in the literature (in contrast to bond percolation).
My restriction to the positive orthant is not generally followed in the literation, but that
aside, there is much known, and much unknown. In general there is a critical probability
$delta_c$ for each dimension $d$ that answers my first question: for $delta < delta_c$,
the origin belongs to an infinite component, and for $delta > delta_c$, it belongs to a finite
component. Remarkably, exact values for $delta_c$ for site percolation on $mathbb{Z}^d$ for
$d ge 2$ are not known. For $d=2$, it is estimated via numerical simulations to be 0.59;
for $d=3$, it is about 0.31.

No comments:

Post a Comment