7
$\begingroup$

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$?

$\endgroup$
  • $\begingroup$ you need the exact probability? $\endgroup$ – Salomo May 5 '15 at 1:26
  • $\begingroup$ i am doing some reading on this and i think i can be shown that if n is large enough, G has a perfect matching with probability 1-1/n. But i don't know how to get there. $\endgroup$ – David May 5 '15 at 1:28
  • $\begingroup$ I don't think it is possible if you didn't fix $p$, say $p$ can be $0$. $\endgroup$ – Salomo May 5 '15 at 1:31
  • $\begingroup$ true, but what if we fix p=constant * (ln n /n) $\endgroup$ – David May 5 '15 at 1:44
2
$\begingroup$

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}$$

$\endgroup$
  • $\begingroup$ Dear Misha, do you know if there is a textbook or journal reference for this beautiful solution? I've found this one math.cmu.edu/~af1p/Texfiles/matchplusbip.pdf $\endgroup$ – fox May 19 '18 at 22:04
  • $\begingroup$ Probably math.cmu.edu/~af1p/BOOK.pdf should cover it. $\endgroup$ – Misha Lavrov May 19 '18 at 22:17
  • $\begingroup$ Thanks. Does this result implies that when $p=log n/n$, i.e. $c=0$, the probability converges to e^{-2}=.14? $\endgroup$ – fox May 20 '18 at 15:20
  • 1
    $\begingroup$ Yes, it does. (And this is also the limiting probability that there are no isolated vertices.) $\endgroup$ – Misha Lavrov May 20 '18 at 15:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.