0
$\begingroup$

Given a balanced bipartite graph $G_1$ on $2n$ vertices on the condition $PM(G_1)\equiv1\bmod2$, an integer $i$ of size $\Omega(n\log n)$, can we find a balanced bipartite graph $G_2$ on $poly(n)$ vertices in polynomial or quasipolynomial time such that $$PM(G_1)PM(G_2)\equiv1\bmod2^i$$ holds where $PM(G)$ is number of perfect matchings of $G$?

If $i=O(\log(n))$ then the construction involves disjoint union of $CarmichaelLambda(2^i)-1$ copies of $G_1$. So the case I am interested is when $i=\Omega(n\log n)$.

$\endgroup$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.