1
$\begingroup$

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?

$\endgroup$
0
$\begingroup$

This answer shows an approach to the problem in the question.

(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.)

If you prefer not to use that proposition, you can transplant its proof to fit the current problem. It should not be hard to find a proof for that proposition since it is a classic result in the introductory theory of random graphs.

$\endgroup$
  • 1
    $\begingroup$ Thanks! I've found a related work were they actually use the same technique I've been using! $\endgroup$ – Andrea Apr 15 at 14:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.