INTERDISCIPLINARY STOCHASTIC PROCESSES COLLOQUIUM Thursday Nov. 21st 380 Soda 3:10-4:00pm Speaker: J-B Son (University of Edinburgh) Title: Spectral gap and logarithmic Sobolev constant for balanced matroids Abstract: We compute tight lower bounds on the spectral gaps and log-Sobolev constants of a class of inductively defined Markov chains. We can then use spectral gaps and log-Sobolev constants to derive bounds on the rate of convergence of those Markov chains, i.e. the time the Markov chains need to reach their stationary distributions. The Markov chains we define contain the bases-exchange walks for balanced matroids studied by Feder and Mihail. As a corollary, we obtain improved upper bounds for the convergence rate of a variety of Markov chains. An example: the ``natural'' random walk on spanning trees of a graph G as proposed by Broder - which has been studied by a number of authors - converges in time O(mn log n), where n is the number of vertices of G and m the number of edges. This beats the best previous upper bound on this walk by a factor n^2. (joint work with Mark Jerrum)