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

  • Péter Csikvári

    MIT, Cambridge, USA

Abstract

Friedland's Lower Matching Conjecture asserts that if is a -regular bipartite graph on vertices, and denotes the number of matchings of size , then

where . When , this conjecture reduces to a theorem of Schrijver which says that a -regular bipartite graph on vertices has at least

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

In this paper, we prove the Lower Matching Conjecture. In fact, we will prove a slightly stronger statement which gives an extra factor compared to the conjecture if is separated away from and , and is tight up to a constant factor if is separated away from . We will also give a new proof of Gurvits's and Schrijver's theorems, and we extend these theorems to -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