3
$\begingroup$

Is there a lower bound on the number of perfect matchings in a $k$-regular bipartite graph?

One can use Hall's marriage theorem and induction on $k$ to derive the lower bound of $k$. I can't come up with an example where this bound is actually tight. Is there a better lower bound than this?

Improve this question
$\endgroup$
2

1 Answer 1

Reset to default
2
$\begingroup$

as already mentioned in the comments, that is answered by Alexander Schrijver in his publication "Counting 1-factors in regular bipartite graphs":

any $k$-regular bipartite graph with $2n$ vertices has at least $$\left(\frac{(k-1)^{k-1}}{k^{k-2}}\right)^n$$ perfect matchings.

Improve this answer
$\endgroup$
3
  • $\begingroup$ This bound was already given by Anurag in the comments: mathoverflow.net/questions/182989/… $\endgroup$
    – Will Sawin
    Commented May 14, 2022 at 14:04
  • $\begingroup$ @WillSawin sorry, I didn't check the comments for answers. $\endgroup$
    – Manfred Weis
    Commented May 14, 2022 at 14:09
  • $\begingroup$ It's good to have the result written out here, as the links in the comments could die at any time. $\endgroup$
    – Gerry Myerson
    Commented May 15, 2022 at 1:46

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .