Consider $2n$ vertex balanced bipartite graph.


If total number of edges is $n^2$ then we have $n!$ perfect matchings.


Fix $c\in(0,\frac12)$ and consider collection of $2n$ vertex balanced bipartite graphs with at least $cn!$ perfect matchings. What fraction of graphs in this collection have at most $dn^2$ total number of edges in it for some fixed $d\in(0,\frac12)$?


Is there a positive portion of such graphs (if $c\in(0,\frac12)$ can a positive proportion of graphs have $d\in(0,\frac12)$)?



On number of perfect matchings
Even if you have $0.999n^2$ edges, as $n \to \infty$ there can't be $0.0001n!$ matchings. For fixed $c, d \in (0,1)$ and large enough $n=n(c,d)$, among the bipartite graphs with $cn!$ perfect matchings, not only is there not a positive proportion of graphs with at most $dn^2$ edges, there are none at all. 


If there are at most $(1- 2\epsilon)n^2$ edges, then there are at least $\epsilon n$ vertices of degree at most $(1-\epsilon)n$. The number of matchings on such a graph is at most $\left((1-\epsilon)n\right)^{\epsilon n} \left((1-\epsilon)n\right)!$ because we can choose the partners for the $\epsilon n$ vertices of small degree first, and then a matching on the other $(1-\epsilon)n$ vertices.


$$\begin{eqnarray}\frac{\left((1-\epsilon)n\right)^{\epsilon n} \left((1-\epsilon)n\right)!}{n!} &\le& \frac{(1-\epsilon)n}{n} \frac{(1-\epsilon) n}{n-1} ... \frac{(1-\epsilon)n}{n-\epsilon n + 1} \newline & \le & \left(\frac{(1- \epsilon)n}{(1-\epsilon/2)n} \right)^{(\epsilon/2) n} 1^{(\epsilon/2)n}\newline &\le & \left(\left(\frac{1-\epsilon}{1-\epsilon/2} \right)^{\epsilon/2} \right) ^n.\end{eqnarray}$$


If there are at most $(1-2\epsilon)n^2$ edges, then this upper bound for the probability that a random matching is contained in these edges drops exponentially with $n$. So, for any $c,d \in (0,1)$, there are only finitely many $n$ so that there are graphs with at least $cn!$ matchings and at most $dn^2$ edges.


