A Switch Markov Chain for Perfect Matchings (16:30–17:15)

Mark Jerrum ( Queen Mary, University of London )

Motivated by a sampling problem arising in statistics, Diaconis, Graham and Holmes introduced a simple Markov chain, the switch chain, on the set of all perfect matchings in a bipartite graph G. Two basic questions about this Markov chain are: for which class of graphs is the switch chain ergodic, and for which is it rapidly mixing? (I.e., does the switch chain have a limiting distribution and, if so, what is its rate of convergence?) I'll present a precise answer to the ergodicity question and close bounds on the mixing question. In particular, I'll give some rough indications of a proof that the mixing time of the switch chain is polynomial in the size of the graph G in the case that G is monotone (a.k.a. a bipartite permutation graph). The class of monotone graphs includes examples of interest in the statistical setting.

This is joint work with Martin Dyer and Haiko Müller (Leeds).