Minimum planar bipartite graph to cover all perfect matching count

Question

Given set $\mathcal T_n=\{0,1,\dots,2^n-1\}$ what is the minimum number of vertices $2m$ needed in a planar bipartite balanced graph such that at every $i\in\mathcal T_n$ there is a graph $G\in\mathcal G_{2m}$ (set of all bipartite planar balanced graphs on $2m$ vertices) with perfect matching count exactly $i$? Is there a tight upper bound or close form formula or at least is $m=O(n)$?

$\underline{\mbox{Conjectures}}$:

1. For every $\epsilon>0$ there is an $n_\epsilon\in\mathbb N$ such that $\forall n\in\mathbb N_{>n_\epsilon}$ we have $m\leq(1+\epsilon)n$ suffices.

2. Moreover given $n$ the graph representation is in $O(n)$ time.

It is easy to get $m=O(n^2)$ which says nothing about the difficulty of the problem. A lower bound of $m=\Omega(n)$ is shown easily from maximum number of perfect matchings on a planar graph.

I do not know how to do it. However I would think $m=2n$ might even be achievable easily.

I doubt we will solve this without number theoretic knowledge. There is something fundamental missing in representation of natural numbers.

Answer 1

Here is a way to build a balanced, planar, bipartite graph that has exactly $k$ perfect matchings and $O(\log^2 k)$ vertices. First, notice that a ladder graph on $2n$ vertices has exactly $F_n$ perfect matchings, where $F_n$ is the $n$th Fibonacci number:

Also notice that if we remove the top left and either top (if $n$ is even) or bottom (if $n$ is odd) right vertex in the ladder graph, then the remaining graph has exactly 1 perfect matching.

By Zeckendorf's Theorem, every natural number can be expressed uniquely as a sum of distinct Fibonacci numbers. Now, suppose that $k=F_{a_1}+F_{a_2}+\ldots+F_{a_r}$ is the Zeckendorf representation of $k$. Take ladder graphs $L_1,L_2,\ldots,L_r$ on $2a_1, 2a_2,\ldots,2a_r $ vertices, respectively, and identify their top left vertices: call this vertex $v$. Then, identify either top (if $a_i$ is even) or bottom (if $a_i$ is odd) right vertices: call this vertex $w$. Now, this graph has exactly $k$ perfect matchings. If $v$ is matched to a vertex in $L_i$, then we have $F_{a_i}$ ways to complete the matching within $L_i$, and we always force $w$ to be matched to a neighbor in $L_i$. This forces a single perfect matching on the remainder of the graph. Therefore, we have $F_{a_1}+F_{a_2}+\ldots+F_{a_r}=k$ perfect matchings. For example, if $k=9$, then $k=F_1+F_3+F_4$. Then, we glue together ladder graphs on 2, 6 and 8 vertices, respectively. This looks like:

Based on our 3 choices of ladder subgraphs to match $v$ to, we have $F_1=1$, $F_3=3$, or $F_4=5$ possible perfect matchings, giving a total of 9 matchings.

By the fact that $\sum_{i=1}^nF_i=F_{n+1}-2$, $\sum_{i=1}^n i=\Theta(n^2)$ and $F_n=\Theta(\phi^n)$ this gives $O(\log^2 k)$ vertices.

EDIT: Since I misinterpreted the word ``balanced", here is a similar, simpler solution based on the binary representation of $k$. The graph below has $k=7=2^0+2^1+2^2$ perfect matchings. We still have $O(\log^2 k)$ vertices.