The ACO Seminar (2017–2018)

We will examine the problem of approximately counting all perfect matchings in hereditary classes of (nonbipartite) graphs. In particular, we consider the convergence of the switch Markov chain proposed by Diaconis, Graham and Holmes. We determine the largest hereditary class for which this chain is ergodic, and define a large new hereditary class of graphs for which it is rapidly mixing. We show further that the chain has exponential mixing time for slightly larger classes. We will also discuss the question of ergodicity of the switch chain in arbitrary graphs.

Before the talk, at 3:10pm, there will be tea and cookies in Wean 6220.