2
$\begingroup$

Let's $G=(U,V,E)$ be a random balanced Bipartite graph graph which $|U|=|V|=n$.

What is the number of random graphs that has a perfect matching?

I think that the number of possible graphs is $2^{n^2}$, but I can't find how many of them has a perfect match.

  • 0
    This is a research-level question, I'm afraid. To my knowledge, the best known results on this question are asymptotic results, not exact ones. In addition to the Frieze paper linked to by Joseph Malkevitch above, see also [this paper](http://www.math.cmu.edu/~af1p/Texfiles/matchplusnon.pdf) by Frieze and Pittel. In particular, see the classic result of Erdős and Rényi cited in the first paragraph.2012-10-27

0 Answers 0