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_5: 
  @cite_7: We study the behavior of the random walk on the infinite cluster of independent long-range percolation in dimensions d= 1,2, where x and y are connected with probability ( ). We show that if d s>2d, then there is no infinite cluster at criticality. This result is extended to the free random cluster model. A second corollary is that when d≥& 2 and d>s>2d we can erase all long enough bonds and still have an infinite cluster. The proof of recurrence in two dimensions is based on general stability results for recurrence in random electrical networks. In particular, we show that i.i.d. conductances on a recurrent graph of bounded degree yield a recurrent electrical network.
  @cite_11: We provide an estimate, sharp up to poly-logarithmic factors, of the asymptotic almost sure mixing time of the graph created by long-range percolation on the cycle of length N ( @math ). While it is known that the asymptotic almost sure diameter drops from linear to poly-logarithmic as the exponent s decreases below 2 [4, 9], the asymptotic almost sure mixing time drops from N2 only to Ns-1 (up to poly-logarithmic factors).
summary: Further motivation comes from the recent interest in diffusive properties of graphs arising via long-range percolation. An early work in this respect was that of Berger @cite_7 who characterized regimes of recurrence and transience for the simple random walk on such graphs. Benjamini, Berger and Yadin @cite_11 later showed that the mixing time @math of the random walk on @math in @math scales like with an apparent jump in the exponent when @math passes through 2. Misumi @cite_5 found estimates on the effective resistance in @math that exhibit a similar transition.