On number of perfect matchings 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)$)?
 A: 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.
A: Let the two parts be $a_1, \ldots, a_n$ and $b_1, \ldots, b_n$.
Consider taking a random permutation $\pi$ of $[1, \ldots, n]$.
Your condition says that with probability $\ge c$, $[a_1, b_{\pi 1}]$, $[a_2, b_{\pi 2}]$, ... $[a_n, b_{\pi n}]$ is a perfect matching, i.e. these are all edges of your graph. Now if fewer than $cn^2$ of all the pairs $[a_i, b_j]$ were edges, some $a_i$ would have degree less than $cn$, and then the probability of success with a random permutation would be less than $c$.
We conclude that all $n \times n$ bipartite graphs with at least $c n!$ perfect matchings must have at least $cn^2$ edges.
A: Consider any bipartite graph with at least $c n!$ perfect matchings. Each such perfect matching contributes $n$ edges. By double counting, each edge lies in at most $(n-1)!$ matchings. So we have at least
$$
n \frac{c n!}{(n-1)!} = c n^2 \quad \text{edges}.
$$
