# Singleton in a simple SBM

I can't work out the solution to the following exercise:

We have $$2n$$ vertices grouped in $$2$$ clusters of equal size. The probability of having an edge between $$i$$ and $$j$$ is $$p$$ if $$i$$ and $$j$$ are in the same cluster and $$q$$ otherwise. This is a simple SBM with $$2$$ clusters. The problem ask to show that if $$(p+q) << \log(n)/n$$, the probability of having a singleton in the realization of this SBM goes to $$1$$ has n goes to infinity.

Here $$(p+q) << \log(n)/n$$ means that $$f(n) = p(n) + q(n)$$ has a function of $$n$$ satisfy $$\underset{n \rightarrow \infty}\lim \frac{f(n)}{\log(n)/n} = 0$$.

I've been trying the following approach. Let $$S$$ the event we are interested in and for any vertex $$i$$ let $$X_i$$ be the indicator random variable of the event $$i$$ is singleton. Define $$X = \sum_{i} X_i$$, then $$\mathbb{P}(S) = 1 - \mathbb{P} (X = 0)$$. Since $$X$$ is non negative, then $$\mathbb{P} (X = 0) \le \frac{\text{Var}[X]}{(\mathbb{E}[X])^2}$$.

In addition, I observe that since $$X_i$$ is binary valued, then $$\text{Var}[X_i] \le \mathbb{E}[X_i^2] = \mathbb{E}[X_i]$$. So

$$\text{Var}[X] \le \mathbb{E}[X] + \sum_{i}\sum_{j \ne i}\text{Cov}[X_i, X_j]$$

Computing all the terms I get:

$$\mathbb{E}[X] = 2n(1-p)^{n-1}(1-q)^{n}$$ $$\sum_{i}\sum_{j \ne i}\text{Cov}[X_i, X_j] = n^2q(1-p)^{2n-2}(1-q)^{2n-1} + n(n-1)p(1-p)^{2n-3}(1-q)^{2n} \le n^2(1-p)^{2n-3}(1-q)^{2n-1}(p + q)$$

For the convariances, I've split the cases when $$i$$ and $$j$$ are in the same cluster and when $$i$$ and $$j$$ are in different clusters.

All in all, I get: $$\frac{\text{Var}[X]}{(\mathbb{E}[X])^2} \le \frac{2n(1-p)^{n-1}(1-q)^{n} + n^2(1-p)^{2n-3}(1-q)^{2n-1}(p + q)}{4n^2(1-p)^{2n-2}(1-q)^{2n}}$$

This term doesn't look quite right for what I'm supposed to prove, does it?

(Threshold of isolated vertices) Let $$G(n,p)$$ be a random graph with $$n$$ vertices and each edge is present with probability $$p$$ independently. Suppose that $$p\le c{\log n}/n$$ for some constant $$c$$. Then the possibility of the appearance of at least one isolated vertex in $$G(n, p)$$ goes to 1 when $$n$$ goes to infinity.
Assume the above proposition on the threshold of isolated vertices holds. Applying it to the case of $$G(2n, p+q)$$ where $$p+q\le c \log (2n)/2n$$, we know the appearance of at least one isolated vertex goes to 1 when $$2n$$ goes to infinity.
Since the random graph in the question has less edges than the random graph above, the appearance of at least one isolated vertex in the random graph in the question also goes to 1 when $$n$$ goes to infinity. (This loose argument can be made rigorous.)