Counting perfect matchings via random matrices

Estimating the number of perfect matchings in a bipartite graph is a well-known computer science problem, and there is a number of algorithms tackling it. Much less is known about estimating this number for a general graphs with an even number of vertices. Essentially, the only known probabilistic estimator for this problem was constructed by Barvinok, who represented the number of perfect matchings via the determinant of a 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 matrix, under which the Barvinok estimator yields a subexponential error.

Joint work with Alex Samorodnitsky and Ofer Zeitouni.