Succinct polynomial sized representation of balanced bipartite graphs whose perfect matching count is a primorial Is there a $P$ time definable sequence of succinct polynomial sized representation of balanced bipartite graphs whose number of perfect matchings is a primorial?
For factorial a complete bipartite graph suffices.
Motivations:

*

*The speed of growth of the function defining the sequence might capture prime gap information (for instance it might be able to provide lower bound on worst possible gap).


*Since $n\#\approx 2^{O(n)}$ holds the sequence might be a sequence of planar graphs of sizes $O(n)$ in number of vertices and edges providing a way to count primes better.


*The graphs perhaps satisfy symmetry as these objects usually exist for a reason (for complete balanced bipartites the symmetry group is canonical and perhaps for primorial as well there is a nice symmetry group and perhaps might hint at the construction of these family of bipartite graphs).
Input is $n$ but I seek succinct representation of a fixed family and the representation may be $polylog(n)$ sized expressing an exponentially larger balanced bipartite graph with perfect matching a primorial.

Succinct representation of balanced complete bipartite graphs could be a circuit of $2\lceil\log_2(n)\rceil$ input bits where the first half of the input bits represent one color and other half another color and the circuit trivially answers $1$ for all $n^2$ pairs of inputs to imply all pairs of vertices pairing the colors are connected. A boolean circuit for it is trivial as it always outputs $1$.
 A: Consider the graph $G_k$ with vertex set $$\{u_1, \ldots, u_k, v_1, \ldots, v_k\}$$ and edges $$\{(u_1, v_1), \ldots, (u_1, v_k)\} \cup \{(u_2, v_1), \ldots, (u_k, v_{k-1})\} \cup \{(u_2, v_k), \ldots, (u_k, v_k)\}$$ It has $k$ perfect matchings, because once $u_1$ is assigned to $v_i$ this forces the assignments $$\{(u_2, v_1), \ldots, (u_i, v_{i-1}), (u_{i+1}, v_{i+1}), \ldots, (u_k, v_k)\}$$
Therefore a disjoint union of $G_p$ for all prime $p \le n$ has $n\#$ perfect matchings.
As noted in my earlier comment, this answers the question but disappoints you on all points of the motivation.

For a compact circuit representation similar to the encoding for the complete bipartite graph given in the question, encode both $u_i$ and $v_i$ from $G_p$ as $(p, i)$, so that the full input (the encoding of a $u$ vertex as $(p,i)$ and the encoding of a $v$ vertex as $(q,j)$) is $4 \lceil \lg n \rceil$ bits. Then the circuit needs to encode $$(p = q) \wedge (i = 1 \vee i = j \vee i = j+1)$$Addition of $1$ to a $\lg n$-bit number and equality testing of two $\lg n$-bit numbers can both be done in $O(\lg n)$ gates.
