We have a $d$-regular bipartite graph $G = (X,Y,E)$ with $|X| = |Y| = n$ and $|E| = nd$.
What is an upper bound on the number of perfect matchings of $G$?
$\begingroup$
$\endgroup$
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
2
To elaborate on Tony's answer, for a graph $G$ with an even number of vertices and degree sequence $d_1,\dots,d_n$ the number of matchings in $G$ is at most $\prod_{i=1}^n (d_i!)^{\frac{1}{2d_i}}$, with equality achieved only at graphs which are a disjoint union of complete bipartite graphs. The proof is a consequence of the Bregman inequality for permanents. See "The maximum number of perfect matchings in graphs with a given degree sequence", by Alon and Friedland
Notice that there is a conjecture that something similar holds for the number of matchings of size $t$ where $t$ is not necessarily half the number of vertices. It is conjectured that this is also maximized at disjoint union of complete bipartite graphs, but is open in general (even when we restrict to only bipartite graphs).
answered May 20, 2013 at 23:21
-
$\begingroup$ i just want to have a upper bound for the generally $d$-regular bipartite graph <math>$G = (X,Y,E)$</math> with <math>$|X| = |Y| = n$</math> and <math>$|E| = nd$</math>. <math>$n$</math> may be even or odd or whatever. I just want a formula that is true for all those case. <math>$#M \leq ....$</math> $\endgroup$– pnakyCommented May 21, 2013 at 10:04
-
$\begingroup$ @pnaky: Gjergji's answer is close to the best you can do. If $d$ is a divisor of $n$, it is exactly the best you can do. Just set all the $d_i$s equal to $d$. $\endgroup$ Commented May 21, 2013 at 14:22
$\begingroup$
$\endgroup$
6
In the case that $2d$ divides $n$, one can take $G$ to be $\frac{n}{2d}$ disjoint copies of $K_{d,d}$. This graph has $(d!)^{n/2d}$ perfect matchings, and as Gjergji's answer shows, this is the worst case.
answered May 20, 2013 at 23:04
-
$\begingroup$ it is only for the case that d divide n? $\endgroup$– pnakyCommented May 24, 2013 at 12:28
-
$\begingroup$ For your special case, your degree sequence is $d,d,\dots. d$, so Gjergji's answer shows that there are at most $(d!)^{n/d}$ perfect matchings. This works even if $d$ does not divide $n$. My answer shows examples where you can achieve this bound. Gjergji's answer says that these are the only graphs that achieve the upper bound. This is really the end of the story. Your question has been completely answered. $\endgroup$ Commented May 24, 2013 at 19:19
-
$\begingroup$ Don't you mean "one can take $G$ to be $\frac{n}{2d}$ disjoint copies of $K_{d,d}$"? $\endgroup$– UntitledCommented Oct 9, 2014 at 7:21
-
$\begingroup$ Yes, thanks. I edited accordingly. $\endgroup$ Commented Oct 9, 2014 at 9:34
-
1$\begingroup$ @Evgenii.Balai Yes. Thanks! I edited the answer. $\endgroup$ Commented Sep 8, 2021 at 1:30