The diameter of a long range percolation graph

Details The diameter of a long range percolation graph The diameter of a long range percolation graph

2001-12-04

arxiv.org/abs/math/0112029v1

Mathematics

Probability

To appear in Symposium on Discrete Algorithms, 2002

Scientific paper

We consider the following long range percolation model: an undirected graph with the node set $\{0,1,...,N\}^d$, has edges $(\x,\y)$ selected with probability $\approx \beta/||\x-\y||^s$ if $||\x-\y||>1$, and with probability 1 if $||\x-\y||=1$, for some parameters $\beta,s>0$. This model was introduced by Benjamini and Berger, who obtained bounds on the diameter of this graph for the one-dimensional case $d=1$ and for various values of $s$, but left cases $s=1,2$ open. We show that, with high probability, the diameter of this graph is $\Theta(\log N/\log\log N)$ when $s=d$, and, for some constants $0<\eta_1<\eta_2<1$, it is at most $N^{\eta_2}$, when $s=2d$ and is at least $N^{\eta_1}$ when $d=1,s=2,\beta<1$ or $s>2d$. We also provide a simple proof that the diameter is at most $\log^{O(1)}N$ with high probability, when $d

Affiliated with

Also associated with

No associations

Rating

The diameter of a long range percolation graph does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The diameter of a long range percolation graph, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The diameter of a long range percolation graph will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-479181