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

Improve this question
$\endgroup$
3
  • $\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, 2016 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, 2016 at 9:49
  • $\begingroup$ @TonyHuynh Thank you corrected my problem. $\endgroup$
    – Turbo
    Apr 22, 2016 at 9:52

3 Answers 3

Reset to default
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.

Improve this answer
$\endgroup$
4
  • $\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, 2016 at 7:33
  • 2
    $\begingroup$ @Turbo: Yes.$ $ $\endgroup$
    – Douglas Zare
    Apr 24, 2016 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, 2016 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, 2016 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.

Improve this answer
$\endgroup$
1
  • $\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, 2016 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}. $$

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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