Combinatorics Date:  Friday, February 01, 2013 Location:  3866 East Hall (4:10 PM to 5:00 PM) Title:  Shelah's bipartite matching algorithm Abstract:   I'll present an algorithm, due to Shelah, for deciding in choiceless polynomial time with counting whether a given bipartite graph admits a complete matching. I'll begin by describing what "choiceless polynomial time with counting" means, and then I'll describe two familiar bipartite matching algorithms that don't qualify: the path-augmenting algorithm isn't choiceless, and the marriage theorem isn't polynomial time. Both of these nevertheless play a role, along with some other ideas, in Shelah's result. Speaker:  Andreas Blass Institution:  University of Michigan Event Organizer:   Sergey Fomin      Edit this event (login required). Add new event (login required). For access requests and instructions, contact math-webmaster@umich.edu Back to previous page Back to UM Math seminars/events page.