Stack Exchange network consists of 183 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.
Visit Stack Exchange
Suppose that the expected number of matchings of size $r$ for some $r \leq n$ is at least $1$. That is, we expect to have a matching of size $r$. By linearity of expectation:
$$1 \leq {n \choose r}^2 {p^{r^{2}}}$$$$1 \leq {n \choose r}^2 r! \ {p^{r}}$$ that is you need to find the asymptotic for $r$ to satisfy $(1/p)^{r^2} \leq {n \choose r}^2$this.
Suppose that the expected number of matchings of size $r$ for some $r \leq n$ is at least $1$. That is, we expect to have a matching of size $r$. By linearity of expectation:
$$1 \leq {n \choose r}^2 {p^{r^{2}}}$$ that is you need to find the asymptotic for $r$ to satisfy $(1/p)^{r^2} \leq {n \choose r}^2$.
Suppose that the expected number of matchings of size $r$ for some $r \leq n$ is at least $1$. That is, we expect to have a matching of size $r$. By linearity of expectation:
$$1 \leq {n \choose r}^2 r! \ {p^{r}}$$ that is you need to find the asymptotic for $r$ to satisfy this.
Suppose that the expected number of matchings of size $r$ for some $r \leq n$ is at least $1$. That is, we expect to have a matching of size $r$. By linearity of expectation:
$$1 \leq {n \choose r}^2 {p^{r^{2}}}$$ that is you need to find the asymptotic for $r$ to satisfy $(1/p)^{r^2} \leq {n \choose r}^2$.
