3
$\begingroup$

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]$?

$\endgroup$
  • $\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 Noel Apr 17 '16 at 7:15
  • $\begingroup$ @JonNoel I am unfamiliar with this theorem. Perhaps you could elaborate below. $\endgroup$ – T.... Apr 17 '16 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 Noel Apr 18 '16 at 23:32
  • $\begingroup$ @JonNoel Seems like it. $\endgroup$ – T.... Apr 19 '16 at 1:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.