2012/05/19 by Liviu Ilinca, Jeff Kahn, Ilinca, Liviu +1
Computer Science · Mathematics · #05C70 #94A17 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1205.4342
openalex publication_date 2012/05/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.