Seminar Event Detail


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

Back to previous page
Back to UM Math seminars/events page.