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

Summary: Friedland's lower matching conjecture asserts that if \(G\) is a \(d\)-regular bipartite graph on \(\nu(G)=2n\) vertices, and \(m_k(G)\) denotes the number of matchings of size \(k\), then \[ m_k(G )\geq {n \choose k}^2\left(\frac{d-p}{d}\right)^{n(d-p)}(dp)^{np}, \] where \(p=\frac{k}{n}\). When \(p=1\), this conjecture reduces to a theorem of \textit{A. Schrijver} [J. Comb. Theory, Ser. B 72, No. 1, 122--135 (1998; Zbl 0905.05060)] which says that a \(d\)-regular bipartite graph on \(\nu(G)=2n\) vertices has at least \[ \left(\frac{(d-1)^{d-1}}{d^{d-2}}\right)^n \] perfect matchings. \textit{L. Gurvits} [Electron. J. Comb. 15, No. 1, Research Paper R66, 25 p. (2008; Zbl 1182.15008)] proved an asymptotic version of the lower matching conjecture, namely he proved that \[ \frac{\ln m_k(G)}{\nu (G)} \geq \frac{1}{2}\left(p \ln \left(\frac{d}{p}\right)+(d-p) \ln \left(1-\frac{p}{d}\right)-2(1-p) \ln (1-p)\right)+o_{\nu (G)}(1). \] In this paper, we prove the lower matching conjecture. In fact, we will prove a slightly stronger statement which gives an extra \(c_p\sqrt{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.