Perfect matching in a random bipartite graph with edge probability 1/2 I am trying to prove that, when given a bipartite graph $G=(X \cup Y, E)$ with $|X|=|Y|=n$ and edge probability $\frac{1}{2}$, as $n\rightarrow \infty$ the probability of the graph having a perfect matching approaches 1. 
After looking at this question, my inclination is to use Hall's theorem, although I can't quite figure out how to prove this.
 A: My answer to the linked question also gives you the proof here, but in the $p = \frac12$ case we can simplify the calculations required.
Our goal is to show that the expected number of sets $S \subseteq X$ or $S \subseteq Y$ with $|N(S)| < |S| \le \frac n2$ goes to $0$. (Here's why it's enough to consider $|S|\le \frac n2$. If $|S| > \frac n2$, say $S \subseteq X$, let $T$ be a subset of $Y \setminus N(S)$ with $n-|S|+1$ elements. Then $N(T) \subseteq X \setminus S$, so $|N(T)| \le n - |S| < |T|$, and we can use $T$ in place of $S$.)  
We can bound this expected number by
$$
    2\sum_{k=1}^{n/2} \binom nk \binom n{k-1} 2^{-k(n-k+1)}
$$
which comes from the following:


*

*We $\sum_{k=1}^{n/2}$ to look at the different possible values of $k = |S|$.

*There are $\binom nk$ ways to pick $S$ and $\binom{n}{k-1}$ ways to pick some set of $k-1$ vertices containing $N(S)$.

*There is a $2^{-k(n-k+1)}$ probability that there are no edges from $S$ to the other $n-k+1$ vertices on the other side.

*We multiply by $2$ because $S$ could be in $X$ or in $Y$.


To show that this goes to $0$, bound $\binom nk \le n^k$, $\binom n{k-1} \le n^k$, and $2^{-k(n-k+1)} \le 2^{-kn/2}$. Then
$$
   2\sum_{k=1}^{n/2} \binom nk \binom n{k-1} 2^{-k(n-k+1)} \le 2 \sum_{k=1}^{n/2} n^{2k} 2^{-kn/2} \le 2 \sum_{k=1}^\infty (n^2 2^{-n/2})^k = 2 \cdot \frac{n^2 2^{-n/2}}{1 - n^2 2^{-n/2}}.
$$
As $n \to \infty$, $n^2 2^{-n/2} \to 0$, and therefore this expected value goes to $0$ as well.
