Department of Mathematical Sciences
Events
People
Colloquia and Seminars
Conferences
Centers
Positions
Areas of Research
About the Department
Alumni |
Algorithms, Combinatorics and Optimization Seminar
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. |