Graph diameter in long-range percolation

Abstract

We study the asymptotic growth of the diameter of a graph obtained by adding sparse "long" edges to a square box in ${\mathbb{Z}}^d$. We focus on the cases when an edge between $x$ and $y$ is added with probability decaying with the Euclidean distance as $|x-y{|}^{-s+o(1)}$ when $|x-y|\to \infty$. For $s\in (d,2d)$ we show that the graph diameter for the graph reduced to a box of side $L$ scales like $(\log L{)}^{\Delta +o(1)}$ where ${\Delta }^{-1}:={\log }_2(2d/s)$. In particular, the diameter grows about as fast as the typical graph distance between two vertices at distance $L$. We also show that a ball of radius $r$ in the intrinsic metric on the (infinite) graph will roughly coincide with a ball of radius $\exp \{r^{1/\Delta +o(1)}\}$ in the Euclidean metric.

17 pages, extends the results of arXiv:math.PR/0304418 to graph diameter, substantially revised and corrected, added a result on volume growth asymptotic

References in corpus (3)

• On the scaling of the chemical distance in long-range percolation models
• Transience, Recurrence and Critical Behavior for Long-Range Percolation
• The growth of the infinite long-range percolation cluster

Cited by in corpus (12)

• Rare region effects in the contact process on networks
• The growth of the infinite long-range percolation cluster
• Sharp asymptotic for the chemical distance in long-range percolation
• Genuine localisation transition in a long-range hopping model
• Long-range percolation on the hierarchical lattice
• Distances in $\frac{1}{|x-y{|}^{2d}}$ percolation models for all dimensions
• Quenched Invariance Principle for a class of random conductance models with long-range jumps
• Arithmetic oscillations of the chemical distance in long-range percolation on ${\mathbb{Z}}^d$
• Long-range contact process and percolation on a random lattice
• Isoperimetric lower bounds for critical exponents for long-range percolation
• Behavior of the distance exponent for $\frac{1}{|x-y{|}^{2d}}$ long-range percolation
• Continuity of the critical value and a shape theorem for long-range percolation