Lower matching conjecture, and a new proof of Schrijver's and Gurvits's theorems
Lower matching conjecture, and a new proof of Schrijver's and Gurvits's theorems
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 Schrijver which says …