Asymptotics of the Upper Matching Conjecture
classification
🧮 math.CO
keywords
graphsupperbestconjecturedegreesmatchingrightarrowspecified
read the original 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) \rightarrow 0$ as $d \rightarrow \infty$. This represents the best progress to date on the "Upper Matching Conjecture" of Friedland, Krop, Lundow and Markstr\"om. Some further possibilities are also suggested.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.