Mixing of random walks and random matroid processes

Igor Pak

Yale University

Febrary 26,
4:15pm
refreshments at 3:45pm
2-338

ABSTRACT 

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

Combinatorics Seminar, Mathematics Department, MIT, sara(at-sign)math.mit.edu

Page loaded on February 01, 1999 at 03:25 PM. Copyright © 1998-99, Sara C. Billey. All rights reserved.