Lower matching conjecture, and a new proof of Schrijver's and Gurvits's theorems

Abstract

Friedland's Lower Matching Conjecture asserts that if G is a d-regular bipartite graph on upsilon(G) = 2n vertices, and m(k)(G) denotes the number of matchings of size k, then m(k)(G) >= (n/k)(2) (d - p/d)(n(d-p)) (dp)(np), where p = k/n. When p = 1, this conjecture reduces to a theorem of Schrijver which says that a d-regular bipartite graph on upsilon(G) = 2n vertices has at least ((d-1)(d-1)/d(d-2))(n) perfect matchings. L. Gurvits proved an asymptotic version of the Lower Matching Conjecture, namely lnm(k)(G)/upsilon(G) >= 1/2 (p ln (d/p) + (d - p) ln (1 - p/d) - 2(1-p) ln(1-p)) + o(upsilon)(G)(1). In this paper, we prove the Lower Matching Conjecture. In fact, we establish a slightly stronger statement which gives an extra c(p root)n factor compared to the conjecture if p is separated away from 0 and 1, and is tight up to a constant factor if p is separated away from 1. We will also give a new proof of Gurvits's and Schrijver's theorems, and we extend these theorems to (a,b)-biregular bipartite graphs.