# Matching in a random graph

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 .

-
So what have you tried? –  draks ... Apr 6 '12 at 10:46
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... –  Clueless Apr 6 '12 at 18:45
Clueless: Show the mathematical expression you got. –  Did Apr 22 '12 at 17:17

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.
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$.. –  Clueless Apr 6 '12 at 18:40