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

Péter Csikvári

doi:10.4171/jems/706

JournalsjemsVol. 19, No. 6pp. 1811–1844

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

Péter Csikvári
MIT, Cambridge, USA

Download PDF

Abstract

Friedland's Lower Matching Conjecture asserts that if $G$ is a $d$ -regular bipartite graph on $ν (G) = 2 n$ vertices, and $m_{k} (G)$ denotes the number of matchings of size $k$ , then

m_{k} (G) \geq (k n)^{2} (\frac{d - p}{d})^{n (d - p)} (d p)^{n p},

where $p = \frac{k}{n}$ . When $p = 1$ , this conjecture reduces to a theorem of Schrijver which says that a $d$ -regular bipartite graph on $ν (G) = 2 n$ vertices has at least

(\frac{( d - 1 ) ^{d - 1}}{d ^{d - 2}})^{n}

perfect matchings. L. Gurvits proved an asymptotic version of the Lower Matching Conjecture, namely he proved that

\frac{ln m _{k} ( G )}{ν ( G )} \geq \frac{1}{2} (p ln (\frac{d}{p}) + (d - p) ln (1 - \frac{p}{d}) - 2 (1 - p) ln (1 - p)) + o_{ν (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} 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.

Cite this article

Péter Csikvári, Lower matching conjecture, and a new proof of Schrijver's and Gurvits's theorems. J. Eur. Math. Soc. 19 (2017), no. 6, pp. 1811–1844

DOI 10.4171/JEMS/706