Nayantara Bhatnagar, Dana Randall, Vijay Vazirani, Eric Vigoda
Random Bichromatic Matchings

Abstract:  Given a graph with edges colored RED and BLUE, we are interested in sampling  and approximately counting the number of perfect matchings with exactly k RED edges.  An interesting special case is when the graph is a region on the 2-dimensional Cartesian lattice and all the horizontal edges are colored RED and the vertical edges are BLUE, so counting such matchings tells us the number of dimer configurations with k horizontal dimers. We study a Markov chain on the space of all matchings of a graph, that favors matchings with k RED edges. We show that it is rapidly mixing using canonical paths that are given by an algorithm for a combinatorial problem (unrelated to matchings). The canonical paths are constructed to allow us to control the number of RED edges in intermediate matchings along the path and hence bound the mixing time. Finally, we show that  this chain can be used to sample dimer configurations of a 2-dimensional toroidal region by proving combinatorial inequalities that relate the numbers of near-perfect and perfect matchings with k RED edges.