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

. 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 | o i n f t y

. For

s i n (d, 2 d)

we show that the graph diameter for the graph reduced to a box of side

L

scales like

(l o g L)^{D e l t a + o (1)}

where

D e l t a^{- 1} := l o g_{2} (2 d / 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

e x p r^{1 / D e l t a + o (1)}

in the Euclidean metric.

Recommendations

Cites work

Cited in

(19)

This page was built for publication: Graph diameter in long-range percolation