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.

  • 1
    You might look at: math.cmu.edu/~af1p/Texfiles/matchplusbip.pdf2012-10-27
  • 0
    What is your random model? Each of the $n^2$ edges is independently chosen to be either present or not, with probability $p = 1/2$?2012-10-27
  • 0
    Each of the n^2 edges is independently chosen to be present with probability p=n/3. but the probability doesn't affect the number of graphs.2012-10-27
  • 0
    You talk about random graphs but really you just mean "What is the number of graphs..." not "random graphs", right? If you want to count the number of "random graphs" that has some property, aren't you just counting the number of "graphs" that has the property? And, if so, then there's no reason to mention anything about random. You might use random graphs to prove something, but the statement has nothing to do with random graphs. Am I misunderstanding something?2012-10-27
  • 0
    you are rignt. I am actually trying to find the probability, but I want to do that as much as I can on my own.2012-10-27
  • 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