The probability of having a perfect matching in a bipartite graph

Question

Say we have a bipartite graph $G$ with two sets, $\{x_1,\dotsc,x_n\}$ and $\{y_1,\dotsc,y_n\}$. For each pair $xy$, there is an edge with probability $p$. Then, what is the probability of having a perfect matching in $G$?

Answer 1

For too-small $p$, there will be isolated vertices, and in particular there will be no perfect matching.

The key range of $p$ to consider for isolated vertices, as we'll see shortly, is $p = \frac{c + \log n}{n}$, for $c$ constant. Here, the probability that a vertex is isolated is $(1-p)^n \sim e^{-pn} = \frac{e^{-c}}{n}$. Moreover, if we fix $k$ vertices (on either side), for $k$ constant, then the probability that all $k$ are isolated is between $(1-p)^{kn}$ and $(1-p)^{kn - (k/2)^2}$, which are both $\sim (e^{-pn})^k = \frac{e^{-ck}}{n^k}$. So the expected number of $k$-sets of vertices that are isolated - the $k^{\text{th}}$ factorial moment of the number of isolated vertices - is $$\binom{2n}{k} \cdot \frac{e^{-ck}}{n^k} \sim \frac{(2 e^{-c})^k}{k!}.$$ By the method of moments, this proves that as $n \to \infty$, the number of isolated vertices is asymptotically Poisson with mean $2 e^{-c}$, which means in particular that the probabiltiy of having no isolated vertices is $e^{-2e^{-c}}$ in the limit.

I claim that actually, this is also the probability (in the limit) of having a perfect matching in the graph. To do this, we check Hall's condition.

We want to see if there is a set $S \subseteq X$ with $|N(S)| \le |S|$. We may assume $S$ is minimal with this property, which means that $|N(S)| = |S|-1$ (otherwise we could delete any vertex in $S$) and that every vertex in $N(S)$ has at least two neighbors in $S$ (otherwise we could delete that vertex and its only neighbor in $S$). Separately, at the cost of a factor of $2$, we may assume $|S| \le \frac n2$, otherwise we could pass to the set $T = Y \setminus N(S)$ and check Hall's condition for (a minimal subset of) $T$. Finally, we may assume $|S|\ge 2$, since we've already checked the isolated vertices case.

The expected number of such sets is bounded by $$\sum_{k=2}^{n/2} \binom nk \binom n{k-1} \binom{k(k-1)}{2k-2} p^{2k-2} (1-p)^{k(n-k)}.$$ (From the condition that every vertex in $N(S)$ has at least two neighbors in $S$, we can conclude that there are at least $2k-2$ edges between $S$ and $N(S)$, which is worth it for the decrease in probability.)

This sum is going to go to $0$ as $n \to \infty$, though that's tedious to check. Essentially, for small $k$, we lose a factor of $n$ (up to logarithmic factors) with every increase of $k$; we've already seen that $k=1$ is constant, so $k=2$ contributes $\tilde{O}(n^{-1})$ and further $k$ contribute even less. For large $k$, factors like the binomial coefficient in $k$ begin to contribute a lot, but by then we're so far in the "asymptotically irrelevant" hole that we never do catch up.

Therefore cases of Hall's conditition with $|S|\ge 2$ don't asymptotically affect the probability of having a perfect matching. That wraps up the analysis for $p = \frac{c + \log n}{n}$.

For other values of $p$, it's enough to observe that the property of having a perfect matching is monotone increasing, so the probability increases with $p$. Write $p = \frac{f(n) + \log n}{n}$ for an arbitrary function $f(n)$. Then $$\lim_{n\to\infty} \Pr[\text{there is a perfect matching}] =\lim_{n\to\infty} e^{-e^{-f(n)}} = \begin{cases} 0 & f(n) \to -\infty, \\ e^{-2e^{-c}} & f(n) \to c, \\ 1 & f(n) \to \infty. \end{cases}$$