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
    Commented 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
    Commented 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
    Commented 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
    Commented 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
    Commented Apr 20, 2016 at 9:35
  • $\begingroup$ @TonyHuynh mathoverflow.net/questions/239152/…. $\endgroup$
    – user76479
    Commented 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$

You must log in to answer this question.

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