Matching with probabilistic edges Consider two sets $A,B$, each with $n$ vertices. For each pair $(a,b)\in A\times B$, the edge between $a$ and $b$ appears with probability $0.01$, independently of the remaining edges. Is it true that as $n\rightarrow\infty$, the probability that there exists a matching between $A$ and $B$ approaches $1$?
I think it should be true, because for large $n$ the number of options that each vertex from $A$ has in $B$ grows. In particular, the number of options is roughly $0.01n$, and with high probability it is not far from that. Hall's marriage theorem might help, but I'm not sure how.
 A: It is certainly true.
In fact, I believe it should be true if the probability $p$ of an edge, is, say $\frac{4\log n}{n}$. Erdos and Renyi probably proved such a threshold result for perfect matchings in general (i.e. not necessarily bipartite) graphs.
Now some justification: I'll use Hall's theorem and indicate why $|N(S)| \geq |S|$ is true for all sets $S \subset A$ with probability tending to 1. 
Let $S$ be a fixed set of size $s$. Divide $B$ into $s$ sets of equal size. Fix an ordering on both $S$ and the sets of $B$ and consider a set of $s$ perfect matchings between them (pairwise disjoint). For each matching,  we'll try to find a neighbor for any element of $S$ in the corresponding set of $B$. The probability that this cannot be done for any matching is at most $s^s(1-p)^{st}$, where $t=\frac{n}{s}$. The probability that a bad $S$ exists is at most ${(\frac{en}{s})}^{s}s^se^{-pn}$, which goes to zero when $s<< \frac{n}{\log n}$.
If $n \leq 3s$, we can show that $N(S)=B$ with prob tending to 1. We have $ Pr[\exists S: |S|=s, N(S) \neq B] \leq {n \choose s}np^s \leq {(\dfrac{en}{s})}^sn(1-p)^s$; which goes to zero since $(1-p)^s$ dominates the other terms.
[To be continued...]
