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$.

. Does $G_\delta$ contain a simple path from the origin of infinite length?Q1

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$.

. What is $r(d,\delta)$?Q2

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$.

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 and corrections. 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 literature, 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 with positive probability,
and for $\delta > \delta_c$, it belongs to a finite
component with probability $1$.
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.

almost surely'No' for any $\delta > 0$. $\endgroup$ – user5810 May 20 '11 at 10:51