1
$\begingroup$

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:

  1. 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).

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

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

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ Usually, taking $n$ as input and outputting $K_{n,n}$ would not be considered $P$-time, because the input size is $\log n$ and the output size is $\Theta(n^2 \log n)$. If polynomial time in the value of $n$ rather than its encoded size (equivalently: unary input) is acceptable then there's a trivial answer which will disappoint you on all three points of the motivation. $\endgroup$
    – Peter Taylor
    Commented Aug 10, 2021 at 6:45
  • $\begingroup$ Makes sense I provided a better formulation. $\endgroup$
    – Turbo
    Commented Aug 10, 2021 at 12:21

1 Answer 1

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Note the above answer is not for succinct representations. $\endgroup$
    – Turbo
    Commented Aug 10, 2021 at 19:21
  • $\begingroup$ @1.., it is now. $\endgroup$
    – Peter Taylor
    Commented Aug 10, 2021 at 22:29
  • $\begingroup$ I see you index the graph and the edges. Bummer ok. $\endgroup$
    – Turbo
    Commented Aug 11, 2021 at 4:21

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .