|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