# Minimum size of genus $g$ bipartite graphs with $2^n$ perfect matchings

Given $n\in\Bbb Z_{\geq0}$ let $2T_{n,g}$ be size of smallest number of vertices of genus $g$ bipartite graph with $T_{n,g}$ vertices of each color such that number of perfect matchings is $2^n$.

Eg: $T_{0,0}=1$, $T_{1,0}=2$, $T_{2,0}=3$, $T_{3,0}=4$

1. Is there an explicit formula for $T_{n,g}$?

We clearly have $\frac n{W(n)}\leq T_{n,0}\leq 2n$ ($W(n)$ is Lambert $W$) with upper bound achievable.

1. What is the fastest growing function $c(n,g)$ we can have such that $T_{n,g}=\frac n{c(n,g)}$ is possible?

$\frac n{\log_26}<T_{n,0}$ by Petrov's comment.

I think $\frac n{c'\log g}<T_{n,g}<\frac n{c''\log g}$ should be true for some fixed $c',c''>0$.

• In a planar graph on $2T$ vertices the number of perfect matchings does not exceed, say, $6^T$. Indeed, the sum of degrees does not exceed $6\cdot 2T$, choose a part with the sum of degrees at most $6T$, then the product of degrees in this part does not exceed $6^T$. Therefore your $c(n)$ is bounded from below. – Fedor Petrov Jul 1 '17 at 5:50
• @FedorPetrov I was getting something much smaller than $6^T$. It will be nice if you can give the construction for $6^T$ on bipartite graphs. – Turbo Jul 1 '17 at 5:55
• $6^T$ is not a construction, but the upper estimate for the number of perfect matchings. If you get smaller upper estimate, good for you) – Fedor Petrov Jul 1 '17 at 5:57
• I mean my construction does not exceed $2^{T/2}$ by much and so it is just a lower bound not upper. – Turbo Jul 1 '17 at 5:58