Asymptotics of the Upper Matching Conjecture

作者：Ilinca L^*; Kahn J

来源：Journal of Combinatorial Theory - Series A, 2013, 120(5): 976-983.

DOI：10.1016/j.jcta.2013.01.013

• Upper Matching Conjecture
• Entropy
• Asymptotics

We give upper bounds for the number Phi(l)(G) of matchings of size l in (i) bipartite graphs G = (X boolean OR Y, E) with specified degrees d(x) (x is an element of 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 -> infinity. This represents the best progress to date on the "Upper Matching Conjecture" of Friedland, Krop, Lundow and Markstrom.
Some further possibilities are also suggested.

• 出版日期2013-7