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

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

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

There are many $m\in\mathcal N_{2n}$ that do not have a $G\in \mathcal G_{2n}$ such that $f(G)=m$ (refer Are all numbers from $1$ to $n!$ the number of perfect matchings of some bipartite graph?).

How many numbers do we hit or miss in $\mathcal N_{2n}$?

Can $\bigg|{\big\{m\in\mathcal N_{2n}:f^{-1}(m)\cap\mathcal G_{2n}\neq\emptyset\big\}}\bigg|=O(2^{n^c})$ hold for some fixed $c\in(0,1)$?

Conjecture (Update):

$\bigg|{\big\{m\in\mathcal N_{2n}:f^{-1}(m)\cap\mathcal G_{2n}\neq\emptyset\big\}}\bigg|={n^{\Omega(n)}}$ holds.

  • $\begingroup$ Do you know answer for say $n=4$ and $n=5$? Or a fast algorithm for given $m$ to check. $\endgroup$ – kakia Sep 19 '16 at 9:46

Your Answer

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

Browse other questions tagged or ask your own question.