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 b/||x - y||^S if ||x - y|| > 1, and with
probability 1 if ||x - y|| = 1, for some parameters b, 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 V(log N/ log log N) when s = d, and, for some constants 0 < g₁ < g₂ < 1,
it is at most N^g2 when s = 2d, and is at least N^g1 when d = 1, s = 2, b < 1 or when 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 in [2].