Counting Program Seminar Series

This is an extended remix of the talk I gave at SODA last month.

We study a simple Markov chain, the switch chain, on the set of all perfect matchings in a bipartite graph. This Markov chain was proposed by Diaconis, Graham and Holmes as an approach to a sampling problem arising in Statistics. We ask: for which classes of graphs is the Markov chain ergodic and for which is it rapidly mixing? We provide a precise answer to the ergodicity question and close bounds on the mixing question. We show that the mixing time of the switch chain is polynomial in the case of monotone graphs, a class that is of particular interest in the statistical setting.