Matching with probabilistic edges

Question

Let $p<1$ be a constant. 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 $p$, 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 posted this on Math Stackexchange, but after a week of bounty there is still no valid answer. I'm also quite certain that this setting has been considered by Erdős or the likes, but I don't know what it is called. Could someone point me to a reference of this?

Answer 1

A reference is Erdős and Rényi's 1964 paper On Random Matrices, where they show that $p=\frac{\log n}{n}$ is a sharp threshold for the existence of a matching. The idea behind the proof is essentially combining the union bound with careful asymptotics to show that the expected number of sets violating Hall's criterion tends to 0.

The $\frac{\log n}{n}$ here matches the natural lower bound observation that below this probability the graph almost surely has an isolated vertex. Later results of Bollobás and Thomason (described in section 7.3. of Bollobás' Random Graphs book) strengthen this connection to a hitting time result -- if we add edges one by one to the graph, the edge which creates the first perfect matching is with high probability the same edge that removes the last isolated vertex.

Answer 2

Linearity of expectation might be helpful here.

Pick any pairing of vertices, the probability that all of these edges exist is $p^{n}$. So the expected number of matchings must be $n!p^{n}\simeq (\frac{np}{e})^n2\pi n$. If $p$ is constant, and $n\rightarrow \infty$, this expected number of matchings will go up.