The diameter of a long range percolation graph
| dc.creator | Coppersmith, Don | |
| dc.creator | Gamarnik, David | |
| dc.creator | Sviridenko, Maxim | |
| dc.date | 2001-12-04 | |
| dc.date.accessioned | 2026-07-07T04:44:58Z | |
| dc.date.available | 2026-07-07T04:44:58Z | |
| dc.description | 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 β/||\x-\y||^s$ if $||\x-\y||>1$, and with probability 1 if $||\x-\y||=1$, for some parameters $β,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 $Θ(\log N/\log\log N)$ when $s=d$, and, for some constants $0<η_1<η_2<1$, it is at most $N^{η_2}$, when $s=2d$ and is at least $N^{η_1}$ when $d=1,s=2,β<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<s<2d$, established previously by Berger and Benjamini. | |
| dc.description | To appear in Symposium on Discrete Algorithms, 2002 | |
| dc.identifier | https://arxiv.org/abs/math/0112029 | |
| dc.identifier | http://arxiv.org/abs/math/0112029 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/62807 | |
| dc.subject | Probability | |
| dc.subject | Mathematical Physics | |
| dc.subject | Combinatorics | |
| dc.subject | 60C05;60K35;82B43;82B26 | |
| dc.title | The diameter of a long range percolation graph | |
| dc.type | text |