The diameter of a long‐range percolation graph

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 ≈ β/∥ 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 [ 2 ], 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   η   2when s = 2 d, and is at least N   η   1when d = 1, s = 2, β < 1 or when s > 2 d . We also provide a simple proof that the diameter is at most log O (1) N with high probability, when d < s < 2 d, established previously in [2]. © 2002 Wiley Periodicals, Inc. Random Struct. Alg., 21: 1–13, 2002