CMU Campus
Department of         Mathematical Sciences
Events People Colloquia and Seminars Conferences Centers Positions Areas of Research About the Department Alumni
Algorithms, Combinatorics and Optimization Seminar
Martin Dyer
University of Leeds
Title: Matchings and the switch chain

Abstract: 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.

Date: Thursday, May 10, 2018
Time: 3:30 pm
Location: Wean Hall 8220
Note: Before the talk, at 3:10 pm, there will be tea and cookies in Wean Hall 6220.