3
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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:

enter image description here

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:

enter image description here

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.

enter image description here

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.

enter image description here

$\endgroup$
  • $\begingroup$ I realize this does not quite answer your question: I don't immediately see a way to get a smaller number of matchings on a planar balanced bipartite graph on the same number of vertices as this construction, so we haven't shown that your $m$ exists for all $n$. $\endgroup$ – Puck Rombach Dec 8 '18 at 5:53
  • $\begingroup$ $m=100n$ possible? $\endgroup$ – Brout Dec 8 '18 at 6:01
  • $\begingroup$ To clarify, what do you mean by balanced? I was assuming that you meant that $|E(H)|/|V(H)|\leq |E(G)|/|V(G)|$ for all subgraphs $H$ of $G$. $\endgroup$ – Puck Rombach Dec 8 '18 at 6:09
  • $\begingroup$ I am not sure if we can keep the graph balanced, but we can add more vertices without increasing the number of matchings by subdividing any edge twice. If that works then this construction does give a bound for your full question. Even so, the bound is $m=O(n^2)$, so we're not as far down as you'd like. Note that if for example you restricted your set $T_n$ to be a set of Fibonacci numbers you do get down to $m=O(n)$. $\endgroup$ – Puck Rombach Dec 8 '18 at 6:38
  • $\begingroup$ by balanced each color has same number of vertices. $\endgroup$ – Brout Dec 8 '18 at 7:05

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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