Mixing of random walks and random matroid processes
refreshments at 3:45pm
Let A be a set of vectors in d-dimensional space V over
the finite field. Define a random walk on V as follows:
at each step move along a uniform vector in A. We show
that mixing and cutoff of these random walks intimately
related to properties of the random matroid process,
corresponding to A. In case of the graphical matroids,
cutoff phenomenon of random walks follows from the
threshold in random subgraphs. We conclude by discussing
a similar connection between random walk on a symmetric
group generated by transpositions, and random graphs.
Speaker's Contact Info: paki(at-sign)math.yale.edu.zzz - delete .zzz
Return to seminar home page
Page loaded on February 01, 1999 at 03:25 PM.
Copyright © 1998-99, Sara C. Billey.
All rights reserved.