Asymptotically what is the fraction of balanced bipartite graph on $2n$ vertices with at most $cn^{\beta}$ edges having at most $n^\alpha$ perfect matchings for any fixed $c,\alpha>0$ and fixed $\beta\in[1,1.5]$?
$\begingroup$
$\endgroup$
4
-
$\begingroup$ Perhaps you could get a lower bound on this quantity using Brègman's Theorem. It would give you a set of degree sequences that are guaranteed to have a small number of perfect matchings (you'd still have to count balanced bipartite graphs with those degree sequences, though). $\endgroup$– Jon NoelCommented Apr 17, 2016 at 7:15
-
$\begingroup$ @JonNoel I am unfamiliar with this theorem. Perhaps you could elaborate below. $\endgroup$– TurboCommented Apr 17, 2016 at 7:18
-
2$\begingroup$ It is Theorem 1 in this paper: combinatorics.org/ojs/index.php/eljc/article/view/v18i1p10. Like I said, this can only give you a lower bound on the ratio that you are interested in and it's very possible that the bound won't be very good! $\endgroup$– Jon NoelCommented Apr 18, 2016 at 23:32
-
$\begingroup$ @JonNoel Seems like it. $\endgroup$– TurboCommented Apr 19, 2016 at 1:04
Add a comment
|