$\newcommand{\PM}{\mathbb P}$Consider the Erdos-Renyi graph with $n$ vertices and connection probabilities $p_n=a\log(n)/n$ with $a<1/2$. I'm interested in the number of isolated edges. An edge $(u,v)$ is isolated if $u$ and $v$ don't have any other friends except each other. Call the number of isolated edges $L_n$. I want to prove the following
Statement. For all $K>0$ $$\PM(L_n>K)\to 1$$
I really don't know what to do. I know that $(u,v)$ is isolated with probability $p_n(1-p_n)^{2n-4}$, but that is all. I think the idea to solve this problem is to find an "easy" event $A_n$ such that $\PM(A_n)\to 1$ and
$$\PM(L_n>K)\geq \PM(A_n)$$
Or find a smart coupling $\tilde L_n$ such that
$$\PM(L_n>K)\geq \PM(\tilde L_n\geq K)$$
where $\PM(\tilde L_n\geq K)$ is much easier to calculate.
We know that
$$L_n=\sum_{u=1}^n\sum_{v=u+1}^n \mathbf 1\{( u,v) \text{ is isolated } \}$$
Maybe we can couple this with Bernoulli random variables which are i.i.d.. The problem with this approach is that the single indicators in $L_n$ are not independent.
Many thanks for your help!
Best Answer
Here's a sketch that I think is mostly right, though I may have made unjustified approximations that may not hold. Write $X_{ij}$ for the indicator variable that edge $(i,j)$ is isolated, where we take $i<j$. Of course $X_{ii}=0$ for all $i$. From linearity of expectation, as you said $$ \mathbb{E}[L_n]=\sum_{i<j}\mathbb{E}[X_{ij}]={n \choose 2}p_n(1-p_n)^{2n-4}. $$ For $p_n=\frac{a\ln n}{n}$, we have for large $n$, $$ \mathbb{E}[L_n]= {n \choose 2}p_n(1-p_n)^{2n-4}\approx \frac{an\ln n}{2}\exp(-2a\ln n)=\frac{a}{2} n^{1-2a}\ln n. $$ Crucially, because $a<1/2$, this is growing with $n$.
Now let's compute the variance of $L_n$. To do this, we need to compute $\mathbb{E}[X_{ij}X_{kl}]$ for various values of $i,j,k,l$. Observe that if $i=j$ and $k=l$, then $X_{ij}X_{kl}=X_{ij}^2=X_{ij}$, so we get the same computation as before. If $(i,j)$ and $(k,l)$ share a common index, it is not hard to see that $X_{ij}X_{kl}=0$, as such edges share a node so neither can be isolated. The last case is that all indices are distinct. In that case $$ \mathbb{E}[X_{ij}X_{kl}]=\Pr(\text{$(i,j)$ is isolated and $(k,l)$ is isolated}). $$ Considering each node among $i,j,k,l$ at a time, one can check that this happens with probability $p_n^2(1-p_n)^{4n-12}$, as there are exactly two edges we need present (namely $(i,j)$ and $(k,l)$) and exactly $4n-12$ edges we need to not be present (draw a picture if this is not clear). Note that there are exactly ${n \choose 2}{n-2 \choose 2}$ such pairs of indices that are pairwise distinct. Using these calculations, we find \begin{align} \mathbb{E}[L_n^2]&=\mathbb{E}\bigg[\bigg(\sum_{j<k} X_{ij}\bigg)^2\bigg]\\ &=\sum_{i<j,k<l}\mathbb{E}[X_{ij}X_{kl}]\\ &=\sum_{i<j}\mathbb{E}[X_{ij}]+\sum_{\text{$i<j,k<l$ all distinct}} \mathbb{E}[X_{ij}X_{kl}]\\ &=\mathbb{E}[L_n]+{n \choose 2}{n-2\choose 2}p_n^2(1-p_n)^{4n-12}\\ &\approx \mathbb{E}[L_n]+{n \choose 2}^2p_n^2(1-p_n)^{4n-8}\\ &=\mathbb{E}[L_n]+\mathbb{E}[L_n]^2. \end{align} It follows that
$$ \text{Var}[L_n]=\mathbb{E}[L_n^2]-\mathbb{E}[L_n]^2\approx \mathbb{E}[L_n]. $$
Let $\sigma=\text{Var}[L_n]\approx \sqrt{\mathbb{E}[L_n]}$. Using the Chebyshev inequality, for any fixed $k$, we thus find that
$$ \Pr(L_n\leq k)\leq \Pr\bigg(\vert L_n-\mathbb{E}[L_n]\vert> \frac{\mathbb{E}[L_n]-k}{\sigma}\sigma\bigg)\leq \frac{\text{Var}[L_n]}{(\mathbb{E}[L_n]-k)^2}=O(1/\mathbb{E}[L_n])\to 0, $$ giving the desired statement.