The Evolution of the Mixing Rate

Details The Evolution of the Mixing Rate The Evolution of the Mixing Rate

2007-01-17

arxiv.org/abs/math/0701474v1

Mathematics

Combinatorics

15 pages

Scientific paper

In this paper 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 (ln n lnln n)^{1/2}, proving that the mixing time in this case is O((ln 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 O(ln n/ln d). We proved these results during the 2003-04 academic year. Similar results but for constant d were later proved independently by I. Benjamini, G. Kozma and N. Wormald.

Affiliated with

Also associated with

No associations

Rating

The Evolution of the Mixing Rate does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The Evolution of the Mixing Rate, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Evolution of the Mixing Rate will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-120431