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.