Skip to main content
3 of 6
added 216 characters in body; edited title
Turbo
  • 13.9k
  • 1
  • 27
  • 76

Statistics of perfect matching and incremental perfect matchings in bipartite planar graphs?

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

  1. What is the probability distribution or at least mean and variance of number of perfect matchings of bipartite planar graphs with $n$ vertices of each color?

Given bipartite planar graph $G$ with $n$ vertices of each color and with $f(G)$ perfect matchings if we add one vertex of each color and choose new additional edge on condition that the new bipartite graph is planar.

  1. What is the probability distribution or at least mean and variance of number of additional perfect matchings?

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 in general and this too depends on starting graph $G$ and is not a Markov process.

Turbo
  • 13.9k
  • 1
  • 27
  • 76