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_0: The uniform spanning forest (USF) in ℤ d is the weak limit of random, uniformly chosen, spanning trees in [−n, n] d . Pemantle [11] proved that the USF consists a.s. of a single tree if and only if d ≤ 4. We prove that any two components of the USF in ℤ d are adjacent a.s. if 5 ≤ d ≤ 8, but not if d ≥ 9. More generally, let N(x, y) be the minimum number of edges outside the USF in a path joining x and y in ℤ d . Then @math
  @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: Recently, long-range percolation has been invoked as a fruitful source of graphs with non-trivial growth properties. Our interest was stirred by the work of Benjamini and Berger @cite_13 who proposed (and studied) long-range percolation as a model of social networks. It is this context where the graph distance scaling, and volume growth, are particularly of much interest. Thanks to numerous contributions that followed @cite_13 , this scaling is now known for most values of @math and @math . Explicitly, for @math , a corollary to the main result of Benjamini, Kesten, Peres and Schramm @cite_0 asserts that almost surely. As @math , the right-hand side tends to infinity and so, at @math , we expect @math . And, indeed, the precise growth rate in this case has been established by Coppersmith, Gamarnik and Sviridenko @cite_12 , where @math '' means that the ratio of left and right-hand side is a random variable that is bounded away from zero and infinity with probability tending to one.