Limit probability of a complete bipartite random graph $G(n,n,p)$ is connected

Question

I need to calculate the following probability limit for a complete bipartite random graph $G(n,n,p)$ in the Erdos-Renyi model: \begin{equation} \lim_{n\rightarrow\infty}\mathbb{P}[G(n,n,p) \text{ is connected}] \end{equation} when $np=\ln n + w(n)$ where $w(n)\rightarrow -\infty$ when $n\rightarrow\infty$.

I know that the expected value of the number of isolated vertices in $G(n,n,p)$ is: \begin{equation} \mathbb{E}X=2n(1-p)^n \end{equation}

Where X stands for the number of isolated vertices of course.

So the graph $G(n,n,p)$ is connected if it doesn't have any isolated vertices then by Markov inequality:

\begin{equation} \mathbb{P}(X\ge 1)\le \mathbb{E}X \end{equation}

and so substituting the value of $p$ i get:

\begin{eqnarray} \lim_{n\rightarrow\infty}\mathbb{P}[G(n,n,p) \text{ is connected}]&=&\lim_{n\rightarrow\infty}\mathbb{P}(X\ge1)\leq\lim_{n\rightarrow\infty}\mathbb{E}X\\ &=&\lim_{n\rightarrow\infty}2n\bigg(1-\cfrac{\ln n + w(n)}{n}\bigg)^n \end{eqnarray}

My questions are 2 actually:

1- Is correct what i did?

2- If the answer for 1 is YES. How can i calculate that limit?

Thanks in advance!

The variance for the number of isolated vertices is \begin{equation} \mathbb{V}X=4n^2(1-p)^n+2n(n-1)(1-p)^{2n}+n^2(1-p)^{2n-1} \end{equation} And by Chebyshev inequality: \begin{eqnarray} \mathbb{P}(X=0)&\leq&\cfrac{\mathbb{V}X}{(\mathbb{E}X)^2} &\leq&\cfrac{4n^2(1-p)^n+2n(n-1)(1-p)^{2n}+n^2(1-p)^{2n-1}}{4n^2(1-p)^{2n}} \end{eqnarray} And sadly once again i got stuck with the limiting probability any hand on this?

Answer 1

You are right that if $X$ is the number of isolated vertices, then $P(X \geq 1) \leq E[X]$, because $X$ is a non-negative integer-valued random variable.

Note that on the event that $\{X \geq 1\}$, the graph is not connected. Thus $\{X \geq 1\} \subseteq \{G(n,n,p) \text{ is not connected}\}$, and in fact, $$ P(X \geq 1) \leq P(G(n,n,p) \text{ is not connected}). $$

So having an upper bound on $P(X \geq 1)$ will not help us here. In fact, \begin{align*} E[X] &= 2n \left( 1 - p_n \right)^n = 2 \exp \left( \ln n + n \ln \left( 1- p_n \right)\right) \\&= 2 \exp \left( \ln n + n (-p_n + O(p_n^2)) \right) \\ &= 2 \exp \left( -\omega_n + O(\ln^2 n/ n) \right) \to \infty, \end{align*} as $n \to \infty$.

Now it is possible to show that $P(X \geq 1) \to 1$ (and hence, $P(G(n,n,p) \text{ is not connected}) \to 1$) without so much more work. If you calculate the second moment of $X$, you can use Chebyshev's Inequality to get this fact.