Spring 2016

Counting Program Seminar Series

Feb. 5, 2016 2:00 pm3:00 pm

Add to Calendar


Martin Dyer (University of Leeds)


Calvin Lab Room 116

The Switch Markov Chain for Perfect Matchings

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.