5
$\begingroup$

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)$)?

$\endgroup$
  • $\begingroup$ You can take $f$ to be identically $0$. And actually, you have to take $f(c)=0$ for all $c$ since there are graphs with $cn^2$ edges and no perfect matchings. $\endgroup$ – Tony Huynh Apr 22 '16 at 9:42
  • 1
    $\begingroup$ Just take $K_{n,n-1}$ together with an isolated vertex. This has $n(n-1)$ edges, but no perfect matchings. $\endgroup$ – Tony Huynh Apr 22 '16 at 9:49
  • $\begingroup$ @TonyHuynh Thank you corrected my problem. $\endgroup$ – Turbo Apr 22 '16 at 9:52
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ are you claiming if you have $(1-2\epsilon)n^2$ edges we cannot have more than $((1-\epsilon)n)^{\epsilon n}((1-\epsilon)n)!$ perfect matchings? $\endgroup$ – Turbo Apr 24 '16 at 7:33
  • 2
    $\begingroup$ @Turbo: Yes.$ $ $\endgroup$ – Douglas Zare Apr 24 '16 at 8:25
  • $\begingroup$ I think your result shows something stronger. Does it seem even $2^{n^{1+\delta}}$ perfect matchings for any $\delta>0$ (such as $n(\log n)^\alpha$ for some $\alpha\in(0,1)$) implies no fixed $\epsilon$ with $(1-2\epsilon)n^2$ edges? $\endgroup$ – Turbo May 3 '16 at 21:48
  • $\begingroup$ @Turbo: The maximum number of matchings is $n! \lt n^n = 2^{n \log_2 n}$. You can have $(n/2)!$ matchings with about $n^2/4$ edges by adding disjoint edges to a complete bipartite graph with half as many vertices. $(n/2)! \sim \sqrt{\pi n} \left(\frac{n}{2e}\right)^{n/2} \gt e^{(1/2) n \ln n - n}$. $\endgroup$ – Douglas Zare May 4 '16 at 5:28
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thank you. I am more interested in converse type of result. May I ask if $c\in(0,\frac12)$ can a positive proportion of graphs have $d\in(0,\frac12)$? $\endgroup$ – Turbo Apr 22 '16 at 20:14
0
$\begingroup$

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}. $$

$\endgroup$
  • $\begingroup$ We seek a converse type result check Doughlas Zare's and Robert Israel's posts below. $\endgroup$ – Turbo Apr 24 '16 at 6:59
  • 1
    $\begingroup$ Yes. So here $d = c$ and the proprotion is $1$. $\endgroup$ – Danny Nguyen Apr 24 '16 at 7:05
  • $\begingroup$ Doug Zare's answer says $d=c$ is impossible for large enough $n$. $\endgroup$ – Turbo Apr 24 '16 at 7:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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