| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 4655454 | Journal of Combinatorial Theory, Series A | 2013 | 8 Pages |
Abstract
We give upper bounds for the number Φℓ(G) of matchings of size ℓ in (i) bipartite graphs G=(X∪Y,E) with specified degrees dx (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[od(1)N], where od(1)→0 as d→∞. 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.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
