Date: Monday, October 09, 2017
Location: 3866 East Hall (4:00 PM to 5:00 PM)
Title: Exponentially many perfect matchings
Abstract: Consider a bipartite graph where every vertex is connected to three neighbors. Does such a graph have a perfect matching, i.e. a bijection from one vertex set to the other, going only along edges? Yes, by Hall's matching (or "marriage") theorem. Can we do any better than this, i.e. find many perfect matchings? The answer is also yes. We will discuss a recent proof of this result by Leonid Gurvits, via investigating analytic properties of polynomials.
Files:
Speaker: Harry Richman
Institution: University of Michigan
Event Organizer:
