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
    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
    Rattle please help!! @rattle how did you reach that conclusion?2012-04-09