Spring 2019

Counting Matchings via the Capacity Method

Tuesday, Mar. 19, 2019 3:30 pm4:15 pm

Add to Calendar


Jonathan Leake (UC Berkeley)

The notion of the capacity of a polynomial was introduced by Gurvits around 2005, originally to give drastically simplified proofs of the Van der Waerden lower bound for permanents of doubly stochastic matrices and Schrijver's inequality for perfect matchings of regular bipartite graphs. Since this seminal work, capacity has been utilized to bound various combinatorial quantities and to give polynomial-time algorithms to approximate such quantities. These types of results are often proven by giving bounds on how much a particular differential operator can change the capacity of a given polynomial. In this talk, we use this method to give a new proof of Csikvári's lower bound on the number of size-k matchings of a biregular bipartite graph. On the way, we will present tight capacity preservation bounds for real stability preservers, and discuss the implications of this result beyond that of counting matchings.