Friedland's Lower Matching Conjecture

Let GG be a dd-regular bipartite graph on v(G)=2nv(G)=2n vertices, and let mk(G)m_k(G) denote the number of matchings of size kk. Put p=knp=\frac{k}{n}. Friedland's Lower Matching Conjecture.

mk(G)(nk)2(dpd)n(dp)(dp)np.m_k(G)\geq {n \choose k}^2\left(\frac{d-p}{d}\right)^{n(d-p)}(dp)^{np}.

The case p=1p=1 is Schrijver's theorem on perfect matchings, and Gurvits proved an asymptotic version. The paper proves this conjecture, in fact obtaining a slightly stronger bound with an extra cpnc_p\sqrt{n} factor when pp is separated from 00 and 11; it is therefore solved.

Sources & referencesView supporting material

Primary source

Péter Csikvári, “Lower matching conjecture, and a new proof of Schrijver's and Gurvits's theorems”, arXiv:1406.0766 (2017).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.