8
$\begingroup$

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


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

$\endgroup$
3
  • $\begingroup$ For $d=1$, the answer is almost surely 'No' for any $\delta > 0$. $\endgroup$
    – user5810
    May 20, 2011 at 10:51
  • 1
    $\begingroup$ I think you aren't stating the property of the critical probability correctly. For any $\delta>0$ there is always probability at least $\delta^2$ that the origin has no neighbours. A more correct statement is that for $\delta\gt\delta_c$ the origin is in a finite component with probability 1, and for $\delta\lt\delta_c$ the origin is in a finite component with probability less than 1. $\endgroup$ Apr 18, 2017 at 2:40
  • $\begingroup$ @BrendanMcKay: Thank you for the correction, now incorporated. $\endgroup$ Apr 18, 2017 at 10:36

3 Answers 3

9
$\begingroup$

The key word is "percolation" and the literature is vast. Some good general references:

Percolation (2nd ed.). Geoffrey Grimmett, Springer-Verlag, 1999

Percolation and disordered systems. Geoffrey Grimmett, lectures notes from the Saint-Flour summer school, 1996. Available from http://www.statslab.cam.ac.uk/~grg/preprints.html , no.13 in the list of preprints.

Percolation. Béla Bollobás and Oliver Riordan, Cambridge University Press, 2006

(terminology: broadly speaking, "random graph" tends to be used in a situation where there is no underlying geometric or spatial structure, while "percolation" tends to be used where there is some sort of underlying lattice or regular structure. But this is not a precise distinction and usage varies).

$\endgroup$
1
6
$\begingroup$

Hi Joseph,

I think the literature about independent site percolation model is relevant for your questions. There is a nice book, that address yours questions in this post. Percolation by Geoffrey Grimmett.

For the question 1, I know you can show the existence of the infinite cluster by a Peierls type argument that is explained in this book.

$\endgroup$
1
  • $\begingroup$ Thank you James & Leandro: I am retrieving Grimmet's book from our library today! $\endgroup$ Aug 16, 2010 at 13:46
3
$\begingroup$

For an accessible introduction to percolation theory see the course handout at https://www.jyu.fi/science/muut_yksikot/summerschool/en/history/JSS19/courses/MA/main#ma2-percolation-theory by Jeffrey Steif.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.