text: We study the asymptotic growth of the diameter of a graph obtained by adding sparse “long” edges to a square box in article amsmath,amsfonts empty . 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| → ∞. For s ∈ (d, 2d) we show that the graph diameter for the graph reduced to a box of side L scales like (log L)Δ+o(1) where Δ−1 := log2(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 r1 Δ+o(1) in the Euclidean metric. © 2010 Wiley Periodicals, Inc. Random Struct. Alg., 39, 210-227, 2011 (Reproduction, by any means, of the entire article for non-commercial purposes is permitted without charge.)
  @cite_13: Bounds for the diameter and expansion of the graphs created by long-range percolation on the cycle ℤ Nℤ are given. © 2001 John Wiley & Sons, Inc. Random Struct. Alg., 19: 102–111, 2001
  @cite_12: 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 > η2 > 1, it is at most Nη2 when s = 2d, and is at least Nη1 when d = 1, s = 2, β > 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].
summary: For @math , the present paper states @math . Here we note that @math as @math which, formally, is in agreement with . For @math we in turn have @math and so, at @math , a polylogarithmic growth is no longer sustainable. Instead, for the case of the decay @math one expects that where @math varies through @math as @math sweeps through @math . This claim is supported by upper and lower bounds in somewhat restricted one-dimensional cases (Benjamini and Berger @cite_13 , Coppersmith, Gamarnik and Sviridenko @cite_12 ). However, even the existence of a sharp exponent @math has been elusive so far.