Let G be the graph whose nodes are the points of
mathbbZd in the nonnegative orthant (i.e., all
coordinates are ge0), 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 Gdelta be the component connected to o.
Question 1. Does Gdelta 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 dge2.
Some experimentation tentatively suggests that for d=2 and delta=frac12, the answer is again 'No.'
When the answer to Question 1 is 'No,'
let r(d,delta) be the radius of Gdelta, defined to be the expected length of the longest of the shortest paths
from o within Gdelta.
Question 2. What is r(d,delta)?
For d=1, I believe the radius is
suminftyk=1k(1−delta)kdelta=(1−delta)/delta;.
For example, r(1,frac14)=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
deltac for each dimension d that answers my first question: for delta<deltac,
the origin belongs to an infinite component, and for delta>deltac, it belongs to a finite
component. Remarkably, exact values for deltac for site percolation on mathbbZd for
dge2 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