Presented on September 21, 2017 at 11:00 a.m. in the Klaus Advanced Computing Building, room 1116W.
Finally, our small-world network has been studied by @cite_19 in the special case @math . However, the results of @cite_19 are about bootstrap percolation, rather than being about the mixing time of the lazy random walk, which is our concern here.
@cite_19
1973616368 2889042315 2963795525 2032332507
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. 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 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 study the small-world network model of Watts and Strogatz, which mimics some aspects of the structure of networks of social interactions. We argue that there is one non-trivial length-scale in the model, analogous to the correlation length in other systems, which is well-defined in the limit of infinite system size and which diverges continuously as the randomness in the network tends to zero, giving a normal critical point in this limit. This length-scale governs the cross-over from large- to small-world behavior in the model, as well as the number of vertices in a neighborhood of given radius on the network. We derive the value of the single critical exponent controlling behavior in the critical region and the finite size scaling form for the average vertex-vertex distance on the network, and, using series expansion and Pade approximants, find an approximate analytic form for the scaling function. We calculate the effective dimension of small-world graphs and show that this dimension varies as a function of the length-scale on which it is measured, in a manner reminiscent of multifractals. We also study the problem of site percolation on small-world networks as a simple model of disease propagation, and derive an approximate expression for the percolation probability at which a giant component of connected vertices first forms (in epidemiological terms, the point at which an epidemic occurs). The typical cluster radius satisfies the expected finite size scaling form with a cluster size exponent close to that for a random graph. All our analytic results are confirmed by extensive numerical simulations of the model. Appears in Phys. Rev. E 60, 7332-7342 (1999).