Asymptotics of the Upper Matching Conjecture

We give upper bounds for the number Φ ℓ ( G ) of matchings of size ℓ in (i) bipartite graphs G = ( X ∪ Y , E ) with specified degrees d x ( x ∈ 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 ) → 0 as d → ∞ . This represents the best progress to date on the “Upper Matching Conjecture” of Friedland, Krop, Lundow and Markström. urther possibilities are also suggested.