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
    Commented 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
    Commented Apr 22, 2016 at 9:49
  • $\begingroup$ @TonyHuynh Thank you corrected my problem. $\endgroup$
    – Turbo
    Commented 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
    Commented Apr 24, 2016 at 7:33
  • 2
    $\begingroup$ @Turbo: Yes.$ $ $\endgroup$
    – Douglas Zare
    Commented 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
    Commented 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
    Commented 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
    Commented 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
    Commented Apr 24, 2016 at 6:59
  • 1
    $\begingroup$ Yes. So here $d = c$ and the proprotion is $1$. $\endgroup$
    – Danny Nguyen
    Commented Apr 24, 2016 at 7:05
  • $\begingroup$ Doug Zare's answer says $d=c$ is impossible for large enough $n$. $\endgroup$
    – Turbo
    Commented Apr 24, 2016 at 7:08

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .