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.)
For @math one expects @cite_13 the same behavior as for the original graph. And indeed, the linear asymptotic, has been established by Berger @cite_8 . For the nearest-neighbor percolation case, this statement goes back to the work of Antal and Pisztora @cite_9 .
@cite_9 @cite_13 @cite_8
2051522939 1986564122 1580648572 2125271247
Abstract We consider n independent points with a common but arbitrary density f in R d . Two points ( X i , X j ) are joined by an edge when a certain set S ( X i , X j ) does not contain any other data points. The expected number E ( N ) of edges in the graph depends upon n , f and the definition of S . Examples include rectangle, spheres and loons; these lead to the graph of all dominance pairs, the Gabriel graph and the relative neighborhood graph, respectively. Other graphs covered by our analysis include the nearest neighbor graph and the directional nearest neighbor graph. In all cases, we obtain asymptotic lower bounds that do not depend upon f (and are hence useful in all applications involving these graphs, since we usually do not know f ). For sparse graphs, exact asymptotic constants are obtained for E ( N ) that are valid for all densities. We prove large deviation estimates at the correct order for the graph distance of two sites lying in the same cluster of an independent percolation process. We improve earlier results of Gartner and Molchanov and Grimmett and Marstrand and answer affirmatively a conjecture of Kozlov. We consider long-range percolation in dimension @math , where distinct sites @math and @math are connected with probability @math . Assuming that @math is translation invariant and that @math with @math , we show that the graph distance is at least linear with the Euclidean distance. Bootstrap percolation on an arbitrary graph has a random initial configuration, where each vertex is occupied with probability @math , independently of each other, and a deterministic spreading rule with a fixed parameter @math : if a vacant site has at least @math occupied neighbours at a certain time step, then it becomes occupied in the next step. This process is well studied on @math ; here we investigate it on regular and general infinite trees and on non-amenable Cayley graphs. The critical probability is the infimum of those values of @math for which the process achieves complete occupation with positive probability. On trees we find the following discontinuity: if the branching number of a tree is strictly smaller than @math , then the critical probability is 1, while it is @math on the @math -ary tree. A related result is that in any rooted tree @math there is a way of erasing @math children of the root, together with all their descendants, and repeating this for all remaining children, and so on, such that the remaining tree @math has branching number @math . We also prove that on any @math -regular non-amenable graph, the critical probability for the @math -rule is strictly positive.