Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
For $d=1$, the answer is almost surely 'No' for any $\delta > 0$. –  Ricky Demer May 20 '11 at 10:51
add comment

3 Answers

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

share|improve this answer
    
Another suggestion is Grimmett's excellent book Probability on Graphs, still available on his website here: statslab.cam.ac.uk/~grg/books/pgs.html –  Tom LaGatta Aug 16 '10 at 13:54
add comment

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.

share|improve this answer
    
Thank you James & Leandro: I am retrieving Grimmet's book from our library today! –  Joseph O'Rourke Aug 16 '10 at 13:46
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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