What is the asymptotic probability of G(n,0.5) to have exactly two isolated vertices?

Question

What is the asymptotic probability of G(n,0.5) to have exactly two isolated vertices?

Really need some explanation or directions with this one!

Thank you in advance!

Answer 1

There are some easy probabilities to find. (All these can be found just by looking at which edges have to be missing in all of these cases.)

• the probability of a specific vertex $u$ being isolated is $(\frac12)^{n-1}$.
• the probability of two specific vertices $u,v$ both being isolated is $(\frac12)^{2n-3}$.
• the probability of three specific vertices $u,v,w$ all being isolated is $(\frac12)^{3n-6}$.

From this we see that two vertices being isolated is much less likely that one, and three vertices being isolated is much much less likely than two.

Let's consider a simpler problem: what is the probability that exactly one vertex is isolated?

If we sum over all possible vertices, we get $n (\frac12)^{n-1}$. That's an overestimate: there is some overlap between these events. But whenever there is overlap, that corresponds to two or more vertices being isolated. So what's the probability that two or more vertices are isolated?

Well, once again, we can sum over all pairs of vertices, and get $\binom n2 (\frac12)^{2n-3}$. That's still an overestimate, because there's overlap between these events. So if we subtract it from our previous probability, the result $n(\frac12)^{n-1} - \binom n2 (\frac12)^{2n-3}$ is an underestimate of the probability that exactly one vertex is isolated.

From $n(\frac12)^{n-1} - \binom n2 (\frac12)^{2n-3} \le \Pr[\text{exactly one isolated vertex}] \le n (\frac12)^{n-1}$, we conclude that the asymptotic probability is $(1+o(1))n (\frac12)^{n-1}$: the $n (\frac12)^{n-1}$ term dominates the $\binom n2 (\frac12)^{2n-3}$ in the limit as $n \to \infty$. (You should check this.) So our answer to the simpler question is $(1+o(1))n (\frac12)^{n-1}$.

A similar argument can be used to find the asymptotic probability that exactly two vertices are isolated.

---

If we just want to show that the probability tends to $0$, that's much easier and can be done via the expected value. But I disagree with stuart stevenson's comment that this is what the problem is looking for.