Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Hi Guys,

We have a d-regular bipartite Graph $G = (X,Y,E)$ with $|X| = |Y| = n$ and $|E| = nd$. i want to know a Upper Bound of the number of Matching

Thankx

share|improve this question

2 Answers 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).

share|improve this answer
    
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> –  pnaky May 21 '13 at 10:04
    
@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$. –  Brendan McKay May 21 '13 at 14:22

In the case that $d$ 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.

share|improve this answer
    
it is only for the case that d divide n? –  pnaky May 24 '13 at 12:28
    
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. –  Tony Huynh May 24 '13 at 19:19
    
Don't you mean "one can take $G$ to be $\frac{n}{2d}$ disjoint copies of $K_{d,d}$"? –  Untitled Oct 9 at 7:21
    
Yes, thanks. I edited accordingly. –  Tony Huynh Oct 9 at 9:34

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.