Perfect Matchings and Random Determinants

Thursday, March 26, 2015 - 2:00pm - 3:00pm
Lind 305
Mark Rudelson (University of Michigan)
Consider a graph with an even number of vertices. A perfect matching is a splitting of the set of vertices into pairs such that each pair is connected by an edge. The only known polynomial time estimator for the number of perfect matchings was constructed by Barvinok. It estimates this number via the determinant of the random matrix associated to the graph. Barvinok proved that the multiplicative error of this estimator is at most exponential, and this result cannot be improved for general graphs. We provide conditions on the graph, under which the Barvinok estimator yields a subexponential error.

Joint work with Alex Samorodnitsky and Ofer Zeitouni.