Hi Guys,
We have a dregular 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
Hi Guys, We have a dregular 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 


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


In the case that $d$ divides $n$, one can take $G$ to be $n/d$ disjoint copies of $K_{d,d}$. This graph has $(d!)^{n/d}$ perfect matchings, and as Gjergji's answer shows, this is the worst case. 


[Placeholder until I can find the delete button. GRP] 

