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.)
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.
@cite_5 @cite_7 @cite_11
1922672875 2033953301 2889042315 1967591194
We prove a conjecture raised by the work of Diaconis and Shahshahani (1981) about the mixing time of random walks on the permutation group induced by a given conjugacy class. To do this we exploit a connection with coalescence and fragmentation processes and control the Kantorovitch distance by using a variant of a coupling due to Oded Schramm. Recasting our proof in the language of Ricci curvature, our proof establishes the occurrence of a phase transition, which takes the following form in the case of random transpositions: at time @math , the curvature is asymptotically zero for @math and is strictly positive for @math . We show that the measure on markings of Znd, d ≥ 3, with elements of 0, 1 given by i.i.d. fair coin flips on the range @math of a random walk X run until time T and 0 otherwise becomes indistinguishable from the uniform measure on such markings at the threshold T = ½Tcov(Znd). As a consequence of our methods, we show that the total variation mixing time of the random walk on the lamplighter graph Z2 ≀ Znd, d ≥ 3, has a cutoff with threshold ½Tcov(Znd). We give a general criterion under which both of these results hold; other examples for which this applies include bounded degree expander families, the intersection of an infinite supercritical percolation cluster with an increasing family of balls, the hypercube and the Caley graph of the symmetric group generated by transpositions. The proof also yields precise asymptotics for the decay of correlation in the uncovered set. Oliveira conjectured that the order of the mixing time of the exclusion process with @math -particles on an arbitrary @math -vertex graph is at most that of the mixing-time of @math independent particles. We verify this up to a constant factor for @math -regular graphs when each edge rings at rate @math in various cases: (1) when @math or (2) when @math the spectral-gap of a single walk is @math and @math or (3) when @math for some constant @math . In these cases our analysis yields a probabilistic proof of a weaker version of Aldous' famous spectral-gap conjecture (resolved by ). We also prove a general bound which is at worst @math , which is within a @math factor from Oliveira's conjecture when @math . As applications we get new mixing bounds: (a) @math for expanders, (b) order @math for the hypercube @math and (c) order @math for vertex-transitive graphs of moderate growth and for supercritical percolation on a fixed dimensional torus. We prove a law of large numbers for a class of ballistic, multidimensional random walks in random environments where the environment satisfies appropriate mixing conditions, which hold when the environment is a weak mixing field in the sense of Dobrushin and Shlosman. Our result holds if the mixing rate balances moments of some random times depending on the path. It applies in the nonnestling case, but we also provide examples of nestling walks that satisfy our assumptions. The derivation is based on an adaptation, using coupling, of the regeneration argument of Sznitman and Zerner.