2
$\begingroup$

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?

$\endgroup$
8
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ Linearity of Expectation is not enough here -- just because the expected number of matchings goes to infinity does not mean the existence of a matching is guaranteed. For example, if $p=\frac{10}{n}$, then the expected number of matchings tends to infinity. However, you can show that with high probability there is not a matching (e.g. because there will likely be isolated vertices in the graph). $\endgroup$ – Kevin P. Costello Nov 5 '15 at 19:47
  • $\begingroup$ Yes, you're right - especially since the existence of different matchings is correlated. Well, that remark might still be useful though. $\endgroup$ – EJI Nov 5 '15 at 20:10

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.