# Maximum number of perfect matchings in a graph of genus $g$ balanced $k$-partite graph

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$$?

• 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 – Dima Pasechnik May 28 '19 at 7:03
• @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. – T.... May 28 '19 at 7:08
• 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. – Dima Pasechnik May 28 '19 at 7:09
• Forgot the reference but check mathoverflow.net/questions/273765/…. – T.... May 28 '19 at 7:22
• 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. – Pat Devlin May 29 '19 at 1:59

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$$.

• Yes... If $g=\log(n)$, then there are at most $10n$ edges, so at most $2^{10n}$ perfect matchings [see case 1]. – Pat Devlin May 29 '19 at 15:38
• Great. In which case the genus is greater than $n$ [see case 2]. – Pat Devlin May 29 '19 at 15:40
• 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. – Pat Devlin May 29 '19 at 15:47
• (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.” – Pat Devlin May 29 '19 at 16:16
• Page $18$ cs.columbia.edu/~cs6204/files/Lec2-Min&MaxGenus.pdf refers. – T.... May 29 '19 at 16:24