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

1

By the Marriage Theorem, $G$ has a perfect matching if and only if $|\Gamma(X)|\ge|X|$ for all $X\subseteq L$. Here, $\Gamma(X)$ denotes the set of neighbours of $X$.

Since the neighbours for each vertex in $L$ are chosen independently (and uniformly), we see that the expected value of $|\Gamma(X)|$ for $X\subseteq L$ is equal to $\frac{n}{100}\cdot |X|$. Hence, the probability for $|\Gamma(X)|\ge |X|$ to hold for all such $X$ tends to $1$ as $n$ grows.

  • 0
    Thanks for the response.. can you be more specific about the part: we see that the expected value of |Γ(X)| for X⊆L is equal to $|X|n/100$ It is possible that two different vertices in X will choose the same vertex in R isn't it? this way it's even possible the value of $|\Gamma(X) |$ is exactly $n/100$..2012-04-06
  • 0
    Rattle please help!! @rattle how did you reach that conclusion?2012-04-09