1
$\begingroup$

What is the maximum number of perfect matchings a genus $g$ balanced $k$-partite graph (number of vertices for each color in all possible $k$-colorings is within a difference of $1$) can have? I am particularly interested in $k=2$.

For planar balanced bipartite graphs (each color has to have same number of vertices assigned) the number of perfect matchings is $2^{O(n)}$ while for genus $\Omega(n^2)$ we can have $2^{\Omega(n\log n)}$. So is maximum number of perfect matchings $2^{O(n\log g)}$ for $k=2$?

$\endgroup$
  • $\begingroup$ genus alone is not a big obstacle, it appears. e.g. fullerens (particular kind of planar graphs) can have exponentially many perfect matchings : arxiv.org/abs/0801.1438 $\endgroup$ – Dima Pasechnik May 28 at 7:03
  • $\begingroup$ @DimaPasechnik You dont get the point. Balanced bipartite graphs can have $2^{\Omega(n\log n)}$ perfect matchings however genus needs to be high and if you have planarity you are constrained by $2^{O(n)}$ perfect matchings. $\endgroup$ – T.... May 28 at 7:08
  • $\begingroup$ planar 4-gonal $2k\times 2k$ grids can have exponentially many perfect matchnigs, too - one covers such a grid by $2\times 2$ squares, each containing a 4-gon, so you can switch each of them in 2 different ways. $\endgroup$ – Dima Pasechnik May 28 at 7:09
  • 1
    $\begingroup$ Forgot the reference but check www.2874565.com/questions/273765/…. $\endgroup$ – T.... May 28 at 7:22
  • 1
    $\begingroup$ The (bipartite) hypercube on $N=2^n$ vertices has genus $1+(n-4)2^{n-3} \approx C N \log(N)$, and it has roughly $2^{c N \log(\log(N))}$ perfect matchings. So there’s something with not huge genus having superexponentialy many perfect matchings. $\endgroup$ – Pat Devlin May 29 at 1:59
1
$\begingroup$

Yes, but not for a great reason.

Fact: genus of a graph is bounded below by $|E|/6 - n/2+1$.

Case 1: suppose $|E| \leq 10 n$. Then the number of perfect matchings is at most ${ {|E|} \choose {n/2}} \leq 2^{|E|} \leq 2^{10n}.$

Case 2: suppose $|E| \geq 10n$ so that (by fact) the genus satisfies $g \geq n$. We know every graph has at most $2^{O(n \log(n))}$ perfect matchings, and we’re done since $g\geq n$.

$\endgroup$
  • $\begingroup$ Yes... If $g=\log(n)$, then there are at most $10n$ edges, so at most $2^{10n}$ perfect matchings [see case 1]. $\endgroup$ – Pat Devlin May 29 at 15:38
  • $\begingroup$ Great. In which case the genus is greater than $n$ [see case 2]. $\endgroup$ – Pat Devlin May 29 at 15:40
  • $\begingroup$ Are you hoping for a construction or a lower bound? If the genus is too small, there are not many edges at all (at most linearly many). And if there are only $cn$ edges, the number of perfect matchings is at most $2^{cn}$, which is in fact less than $2^{cn \log(g)}$. This is a better upper bound than what you were hoping for. So there is no lower bound matching the upper bound hoped for in OP. $\endgroup$ – Pat Devlin May 29 at 15:47
  • 1
    $\begingroup$ (Commenting on “all or nothing” comment) Yea. Seems like it. The upper bounds of $2^{E}$ and $n!$ are always smaller than $2^{n \log(g)}$. I think one of the morals here is that “logs and tolerable multiplicative factors in the exponent cover a multitude of sin.” $\endgroup$ – Pat Devlin May 29 at 16:16
  • 1
    $\begingroup$ Page $18$ cs.columbia.edu/~cs6204/files/Lec2-Min&MaxGenus.pdf refers. $\endgroup$ – T.... May 29 at 16:24

Your Answer

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

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