Math Colloquium: John Wilmes '10, Brandeis University

'Counting Matchings with Markov Chain Monte Carlo' -

Perfect matchings pair each vertex in a graph with exactly one adjacent vertex. The algorithmic problem of counting all perfect matchings in a bipartite graph is famously intractable---it is the prototypical #P-complete problem. Nevertheless, a randomized algorithm due to Jerrum, Sinclair, and Vigoda can efficiently approximately count the number of perfect matchings in a bipartite graph, via a classic application of the Markov Chain Monte Carlo (MCMC) technique. We will take a brief tour through matching theory, computational complexity, and MCMC for sampling and counting combinatorial structures, before describing progress on the problem of approximately counting perfect matchings in general (non-bipartite) graphs.

Thursday, November 7, 2019 at 4:40pm to 5:30pm

Eliot Hall, 314
3203 Southeast Woodstock Boulevard, Portland, Oregon 97202-8199

Event Type

Lecture

Audience

Open to the Public

Department
Mathematics, Division of Mathematical and Natural Sciences
Subscribe
Google Calendar iCal Outlook

Recent Activity