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 1987243055 2117320315 2025859223 2949304946 2021912525 1770148716 2080289118 2063224062 1973616368 2055134178 2039765418 2066678737 2903855202 2139964991 2963795525 2149345630
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. This work proves that the fluctuations of the cover time of simple random walk in the discrete torus of dimension at least three with large side-length are governed by the Gumbel extreme value distribution. This result was conjectured for example in Aldous and Fill (Reversible Markov chains and random walks on graphs, in preparation). We also derive some corollaries which qualitatively describe “how” covering happens. In addition, we develop a new and stronger coupling of the model of random interlacements, introduced by Sznitman (Ann Math (2) 171(3):2039–2087, 2010), and random walk in the torus. This coupling is used to prove the cover time result and is also of independent interest. Suppose that G is a finite, connected graph and X is a lazy random walk on G . The lamplighter chain X ? associated with X is the random walk on the wreath product G ? =Z 2 ?G , the graph whose vertices consist of pairs (f - ,x) where f is a labeling of the vertices of G by elements of Z 2 = 0,1 and x is a vertex in G . There is an edge between (f - ,x) and (g - ,y) in G ? if and only if x is adjacent to y in G and f z =g z for all z?x,y . In each step, X ? moves from a configuration (f - ,x) by updating x to y using the transition rule of X and then sampling both f x and f y according to the uniform distribution on Z 2 ; f z for z?x,y remains unchanged. We give matching upper and lower bounds on the uniform mixing time of X ? provided G satisfies mild hypotheses. In particular, when G is the hypercube Z d 2 , we show that the uniform mixing time of X ? is T(d2 d ) . More generally, we show that when G is a torus Z d n for d=3 , the uniform mixing time of X ? is T(dn d ) uniformly in n and d . A critical ingredient for our proof is a concentration estimate for the local time of the random walk in a subset of vertices. A branching random walk in presence of an absorbing wall moving at a constant velocity v undergoes a phase transition as v varies. The problem can be analyzed using the properties of the Fisher-Kolmogorov-Petrovsky-Piscounov (F-KPP) equation. We find that the survival probability of the branching random walk vanishes at a critical velocity vc of the wall with an essential singularity and we characterize the divergences of the relaxation times for v vc. At v=vc the survival probability decays like a stretched exponential. Using the F-KPP equation, one can also calculate the distribution of the population size at time t conditioned by the survival of one individual at a later time T>t. Our numerical results indicate that the size of the population diverges like the exponential of (vc−v)−1 2 in the quasi-stationary regime below vc. Moreover for v>vc, our data indicate that there is no quasi-stationary regime. Given a discrete random walk on a finite graph @math , the vacant set and vacant net are, respectively, the sets of vertices and edges which remain unvisited by the walk at a given step @math . These sets induce subgraphs of the underlying graph. Let @math be the subgraph of @math induced by the vacant set of the walk at step @math . Similarly, let @math be the subgraph of @math induced by the edges of the vacant net. For random @math -regular graphs @math , it was previously established that for a simple random walk, the graph @math of the vacant set undergoes a phase transition in the sense of the phase transition on Erd os -Renyi graphs @math . Thus, for @math there is an explicit value @math of the walk, such that for @math , @math has a unique giant component, plus components of size @math , whereas for @math all the components of @math are of size @math . We establish the threshold value @math for a phase transition in the graph @math of the vacant net of a simple random walk on a random @math -regular graph. We obtain the corresponding threshold results for the vacant set and vacant net of two modified random walks. These are a non-backtracking random walk, and, for @math even, a random walk which chooses unvisited edges whenever available. This allows a direct comparison of thresholds between simple and modified walks on random @math -regular graphs. The main findings are the following: As @math increases the threshold for the vacant set converges to @math in all three walks. For the vacant net, the threshold converges to @math for both the simple random walk and non-backtracking random walk. When @math is even, the threshold for the vacant net of the unvisited edge process converges to @math , which is also the vertex cover time of the process. Given a finite graph @math , a vertex of the lamplighter graph @math consists of a zero-one labeling of the vertices of @math , and a marked vertex of @math . For transitive @math we show that, up to constants, the relaxation time for simple random walk in @math is the maximal hitting time for simple random walk in @math , while the mixing time in total variation on @math is the expected cover time on @math . The mixing time in the uniform metric on @math admits a sharp threshold, and equals @math multiplied by the relaxation time on @math , up to a factor of @math . For @math , the lamplighter group over the discrete two dimensional torus, the relaxation time is of order @math , the total variation mixing time is of order @math , and the uniform mixing time is of order @math . For @math when @math , the relaxation time is of order @math , the total variation mixing time is of order @math , and the uniform mixing time is of order @math . In particular, these three quantities are of different orders of magnitude. Motivated by the immense success of random walk and Markov chain methods in the design of classical algorithms, we consider quantum walks on graphs. We analyse in detail the behaviour of unbiased quantum walk on the line, with the example of a typical walk, the Hadamard walk''''. In particular, we show that after @math time steps, the probability distribution on the line induced by the Hadamard walk is almost uniformly distributed over the interval @math . This implies that the same walk defined on the circle mixes in linear time. This is in direct contrast with the quadratic mixing time for the corresponding classical walk. We conclude by indicating how our techniques may be applied to more general graphs. Recently, we adapted random walk arguments based on work of Nachmias and Peres, Martin-Lof, Karp and Aldous to give a simple proof of the asymptotic normality of the size of the giant component in the random graph G(n,p) above the phase transition. Here we show that the same method applies to the analogous model of random k -uniform hypergraphs, establishing asymptotic normality throughout the (sparse) supercritical regime. Previously, asymptotic normality was known only towards the two ends of this regime. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2012 © 2012 Wiley Periodicals, Inc. In this note, we demonstrate an instance of bounded-degree graphs of size @math , for which the total variation mixing time for the random walk is decreased by a factor of @math if we multiply the edge-conductances by bounded factors in a certain way. In this article we present a study of the mixing time of a random walk on the largest component of a supercritical random graph, also known as the giant component. We identify local obstructions that slow down the random walk, when the average degree d is at most O( @math ), proving that the mixing time in this case is Θ((n-d)2) asymptotically almost surely. As the average degree grows these become negligible and it is the diameter of the largest component that takes over, yielding mixing time Θ(n-d) a.a.s.. We proved these results during the 2003–04 academic year. Similar results but for constant d were later proved independently by in [3]. © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2008 Most of this work was completed while the author was a research fellow at the School of Computer Science, McGill University. Suppose that G and H are finite, connected graphs, G regular, X is a lazy random walk on G and Z is a reversible ergodic Markov chain on H. The generalized lamplighter chain X* associated with X and Z is the random walk on the wreath product H G, the graph whose vertices consist of pairs (f,x) where f=(f_v)_ v V(G) is a labeling of the vertices of G by elements of H and x is a vertex in G. In each step, X* moves from a configuration (f,x) by updating x to y using the transition rule of X and then independently updating both f_x and f_y according to the transition probabilities on H; f_z for z different of x,y remains unchanged. We estimate the mixing time of X* in terms of the parameters of H and G. Further, we show that the relaxation time of X* is the same order as the maximal expected hitting time of G plus |G| times the relaxation time of the chain on H. We study properties of multiple random walks on a graph under various assumptions of interaction between the particles. To give precise results, we make the analysis for random regular graphs. The cover time of a random walk on a random @math -regular graph was studied in [C. Cooper and A. Frieze, SIAM J. Discrete Math., 18 (2005), pp. 728-740], where it was shown with high probability (whp) that for @math the cover time is asymptotic to @math , where @math . In this paper we prove the following (whp) results, arising from the study of multiple random walks on a random regular graph @math . For @math independent walks on @math , the cover time @math is asymptotic to @math , where @math is the cover time of a single walk. For most starting positions, the expected number of steps before any of the walks meet is @math . If the walks can communicate when meeting at a vertex, we show that, for most starting positions, the expected time for @math walks to broadcast a single piece of information to each other is asymptotic to @math as @math . We also establish properties of walks where there are two types of particles, predator and prey, or where particles interact when they meet at a vertex by coalescing or by annihilating each other. For example, the expected extinction time of @math explosive particles ( @math even) tends to @math as @math . The case of @math coalescing particles, where one particle is initially located at each vertex, corresponds to a voter model defined as follows: Initially each vertex has a distinct opinion, and at each step each vertex changes its opinion to that of a random neighbor. The expected time for a unique opinion to emerge is the same as the expected time for all the particles to coalesce, which is asymptotic to @math . Combining results from the predator-prey and multiple random walk models allows us to compare expected detection times of all prey in the following scenarios: Both the predator and the prey move randomly, the prey moves randomly and the predators stay fixed, and the predators move randomly and the prey stays fixed. In all cases, with @math predators and @math prey the expected detection time is @math , where @math is the @math th harmonic number. 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. Abstract In this paper a random graph model G Z N 2 , p d is introduced, which is a combination of fixed torus grid edges in ( Z ∕ N Z ) 2 and some additional random ones. The random edges are called long, and the probability of having a long edge between vertices u , v ∈ ( Z ∕ N Z ) 2 with graph distance d on the torus grid is p d = c ∕ N d , where c is some constant. We show that, whp, the diameter D ( G Z N 2 , p d ) = Θ ( log N ) . Moreover, we consider a modified non-monotonous bootstrap percolation on G Z N 2 , p d . We prove the presence of phase transitions in mean-field approximation and provide fairly sharp bounds on the error of the critical parameters. We consider a finite random walk on a weighted graph G; we show that the fraction of time spent in a set of vertices A converges to the stationary probability @math with error probability exponentially small in the length of the random walk and the square of the size of the deviation from @math . The exponential bound is in terms of the expansion of G and improves previous results of [D. Aldous, Probab. Engrg. Inform. Sci., 1 (1987), pp. 33--46], [L. Lovasz and M. Simonovits, Random Structures Algorithms , 4 (1993), pp. 359--412], [M. Ajtai, J. Komlos, and E. Szemeredi, Deterministic simulation of logspace, in Proc. 19th ACM Symp. on Theory of Computing, 1987]. We show that taking the sample average from one trajectory gives a more efficient estimate of @math than the standard method of generating independent sample points from several trajectories. Using this more efficient sampling method, we improve the algorithms of Jerrum and Sinclair for approximating the number of perfect matchings in a dense graph and for approximating the partition function of a ferromagnetic Ising system, and we give an efficient algorithm to estimate the entropy of a random walk on an unweighted graph. We introduce a model of random interlacements made of a countable collection of doubly infinite paths on ℤ d ,d > 3. A nonnegative parameter u measures how many trajectories enter the picture. This model describes in the large N limit the microscopic structure in the bulk, which arises when considering the disconnection time of a discrete cylinder (ℤ Nℤ) d-1 x ℤ by simple random walk, or the set of points visited by simple random walk on the discrete torus (ℤ Nℤ) d at times of order u N d . In particular we study the percolative properties of the vacant set left by the interlacement at level u, which is an infinite connected translation invariant random subset of ℤ d . We introduce a critical value u * such that the vacant set percolates for u u * . Our main results show that u * is finite when d > 3 and strictly positive when d > 7. In this paper, we consider a popular randomized broadcasting algorithm called push-algorithm defined as follows. Initially, one vertex of a graph G=(V,E) owns a piece of information which is spread iteratively to all other vertices: in each timestep t=1,2,… every informed vertex chooses a neighbor uniformly at random and informs it. The question is how many time steps are required until all vertices become informed (with high probability). For various graph classes, involved methods have been developed in order to show an upper bound of @math on the runtime of the push-algorithm, where N is the number of vertices and @math denotes the diameter of G. However, no asymptotically tight bound on the runtime based on the mixing time of random walks has been established. In this work we fill this gap by deriving an upper bound of @math , where @math denotes the mixing time of a certain random walk on G. After that we prove upper bounds that are based on certain edge expansion properties of G. However, for hypercubes neither the bound based on the mixing time nor the bounds based on edge expansion properties are tight. That is why we develop a general way to combine these two approaches by which we can deduce that the runtime of the push-algorithm is Θ(log N) on every Hamming graph.