Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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 .

share|improve this question
    
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

1 Answer 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.

share|improve this answer
    
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
    
Rattle please help!! @rattle how did you reach that conclusion? –  Clueless Apr 9 '12 at 12:50

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.