Skip to main content
1 of 6
Turbo
  • 13.9k
  • 1
  • 27
  • 76

Increments of perfect matching?

Given bipartite graph $G$ with $f(G)$ perfect matchings if we add one vertex of each color and with probability $p$ choose every new additional edge then what is the 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)$).

Turbo
  • 13.9k
  • 1
  • 27
  • 76