2
$\begingroup$

Planar graph permanent can be reduced to determinants and so statistics should be amenable.

Pick a uniformly random bipartite planar graph $G$ with $n$ vertices of each color and choose new additional edge on condition that the new bipartite graph $H$ is planar. Denote $f(G)$ and $f(H)$ to number of perfect matchings of each color respectively. The probability distribution of $G$ is different from $H$ since $H$ is no longer picked from uniform distribution.

What is the probability distribution or at least mean and variance of

  1. number of perfect matchings $f(G)$

  2. number of perfect matchings $f(H)$ (note the probability distribution of $H$ is different from $G$)

  3. number of additional perfect matchings $f(H) - f(G)$?

Note number of additional perfect matchings is not a Markov process (it depends on $f(G)$).

Also since number of edges of planar bipartite graphs are bound we do not have much room to draw edges of $H$ in general and this too depends on starting graph $G$ and is not a Markov process.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.