3
$\begingroup$

Hi can anyone help me? nothing I tried worked so far

We build the following random graph: G=(L∪R,E) be a bipartite random graph when |L|=|R|=n. Each vertex v∈L chooses randomly and independently with other vertices in L exactly n/100 neighbours in R. Prove that with probability 1−o(1) there exists a perfect matching in G .

  • 0
    I tried showing that the probability the marriage theorem fails when n goes to infinity is 0. the problem is the mathematical expression I got became very complicated, so I figures there must be something wrong...2012-04-06
  • 0
    Clueless: Show the mathematical expression you got.2012-04-22

1 Answers 1