Asymptotics of the Upper Matching Conjecture

Abstract

We give upper bounds for the number ${\Phi }_{\ell }(G)$ of matchings of size $\ell$ in (i) bipartite graphs $G=(X\cup Y,E)$ with specified degrees $d_x$ ($x\in X$), and (ii) general graphs $G=(V,E)$ with all degrees specified. In particular, for $d$-regular, $N$-vertex graphs, our bound is best possible up to an error factor of the form $\exp [o_d(1)N]$, where $o_d(1)\to 0$ as $d\to \infty$. This represents the best progress to date on the "Upper Matching Conjecture" of Friedland, Krop, Lundow and Markström. Some further possibilities are also suggested.

11 pages

References in corpus (2)

• An upper bound for the number of perfect matchings in graphs
• The maximum number of perfect matchings in graphs with a given degree sequence