7
$\begingroup$

Let $f(G)$ give the number of perfect matchings of a graph $G$.

Consider set $\mathcal N_{2n}=\{0,1,2,\dots,n!-1,n!\}$.

Consider collection of all $2n$ vertex balanced bipartite graph to be $\mathcal G_{2n}$.

For every $m\in\mathcal N_{2n}$ is there a $G\in \mathcal G_{2n}$ such that $f(G)=m$?

Improve this question
$\endgroup$
2
  • $\begingroup$ @how may numbers we miss? he gave a bound. $\endgroup$
    – Turbo
    May 1, 2016 at 0:42
  • $\begingroup$ @Yemon Choi Well, the question of how many numbers are missed was only edited in after I answered the initial question. Thanks for trying to get my answer accepted. For me, it's fine that the question was refined instead of a new question being asked. $\endgroup$
    – Tony Huynh
    May 17, 2016 at 22:47

2 Answers 2

Reset to default
10
$\begingroup$

No. For all $n \geq 3$, there is no $G \in \mathcal{G}_{2n}$ with $f(G)=n!-1$. To see this, note that $f(K_{n,n})=n!$ and $f(K_{n,n}-e)=n!-(n-1)!$, where $K_{n,n}-e$ is $K_{n,n}$ minus an edge. Thus, there are no graphs $G$ in $\mathcal{G}_{2n}$ with $n!-(n-1)!+1, n!-(n-1)!+2 \dots$, or $n!-1$ perfect matchings

Improve this answer
$\endgroup$
4
  • $\begingroup$ Interesting how many integers do we miss in $\mathcal N_{2n}$? $\endgroup$
    – Turbo
    Apr 20, 2016 at 8:42
  • $\begingroup$ $n=3$ $n!-(n-1)!+2=3!-2!+2=6$ for which we have an example. $\endgroup$
    – Turbo
    Apr 20, 2016 at 8:48
  • $\begingroup$ @Turbo The sequence runs from $n!-(n-1)!+1$ to $n!-1$. For $n=3$, we have $n!-(n-1)!+2>n!-1$, so the sequence stops before reaching $n!-(n-1)!+2$ and contains exactly one term (which happens to be $5$). Note that we miss around $(n-1)!$ values of $f(G)$ just from this observation. $\endgroup$
    – Tony Huynh
    Apr 20, 2016 at 9:35
  • $\begingroup$ @TonyHuynh mathoverflow.net/questions/239152/…. $\endgroup$
    – user76479
    May 18, 2016 at 10:52
2
$\begingroup$

Consider $A$ the order $n$ adjacency matrix which has 1 in the $i,j$th entry if there is an edge in the bipartite graph $G$ from top vertex $i$ to bottom vertex $j$, 0 if not. Then the permanent of $A$ counts the number of perfect matchings in $G$. One now sees that any such bipartite graph missing $k\lt n$ edges is a multiple of $(n-k)!$, which has some significance when $k$ is small. In particular when $k=2$, the number of matchings is a multiple of $(n-2)!$. So the feasible values near $n!$ are indeed few in number.

Elsewhere (Number of unique determinants for an NxN (0,1)-matrix) I talk about the determinant spectrum problem for order $n$ $0-1$ matrices; a similar problem for permanents can be and probably has been asked, for which I would like to see references.

Gerhard "Ask Me About Multilinear Functions" Paseman, 2016.05.18.

Improve this answer
$\endgroup$

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.