Return to Question

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

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

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

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

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

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

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

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.

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

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.

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

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

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

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

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

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!

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

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.