Explicit expanders with cutoff phenomena

Details Explicit expanders with cutoff phenomena Explicit expanders with cutoff phenomena

2010-03-18

arxiv.org/abs/1003.3515v1

Mathematics

Probability

17 pages, 2 figures

Scientific paper

The cutoff phenomenon describes a sharp transition in the convergence of an ergodic finite Markov chain to equilibrium. Of particular interest is understanding this convergence for the simple random walk on a bounded-degree expander graph. The first example of a family of bounded-degree graphs where the random walk exhibits cutoff in total-variation was provided only very recently, when the authors showed this for a typical random regular graph. However, no example was known for an explicit (deterministic) family of expanders with this phenomenon. Here we construct a family of cubic expanders where the random walk from a worst case initial position exhibits total-variation cutoff. Variants of this construction give cubic expanders without cutoff, as well as cubic graphs with cutoff at any prescribed time-point.

Affiliated with

Also associated with

No associations

Rating

Explicit expanders with cutoff phenomena 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 Explicit expanders with cutoff phenomena, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Explicit expanders with cutoff phenomena will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-700120