Here $G_{n,p}$ represents the Erdős-Rényi random graph model, where the graph has order $n$ and each edge is added independently with probability $p$. I am faced with proving the following claim:

Show that there is a constant $c>0$ such that, for every $p$ we have:

$\mathbb{P}(G_{n,p}$ is disconnected) $\leq c \mathbb{P}(G_{n,p}$ has an isolated vertex). $\,\,\,(*)$

From the appearance of the question I think it is meant to be interpreted as asking ''in the limit $n \to \infty$''. It is clear that $\mathbb{P}($a fixed vertex of $G_{n,p}$ is isolated$)=(1-p)^{n-1}$. It is easy to calculate the expected number of isolated vertices using this, but I'm not convinced that helps.

As a last thought, a followup to the question asks "What value of $c$ would be acceptable"? It is therefore probably not the case that a valid choice of $c$ will actually be obtained in the proof, although it may be reasonably clear how to calculate one; perhaps that clarifies the nature of the solution a little. Many thanks for your help.

Edit: Update - I have thought a little more about it, and I have the following theorem we can hopefully make use of (if anyone is willing to help me!): suppose $p = \frac{\log{n}+\gamma(n)}{n}$ and $\gamma(n)$ grows at most slowly (say $o(\log \log n)$); then

if $\gamma(n) \to +\infty$, $\mathbb{P}(G_{n,p}$ disconnected)$\to 0$,

if $\gamma(n) \to -\infty$, $\mathbb{P}(G_{n,p}$ disconnected)$\to 1$,

if $\gamma(n) \to k$, $\mathbb{P}(G_{n,p}$ disconnected)$\to 1-e^{-e^{-k}}$.

Now in the first case, being connected implies no isolated vertex, so $(*)$ holds with any constant $c$ since both probabilities are 0. Likewise, in the second case, the graph is almost surely disconnected: while this doesn't immediately imply that an isolated vertex exists, we can hopefully say for $X:=\#$ of isolated vertices,

$\mathbb{E}(X)=n(1-p)^{n-1} = n(1-\frac{\log{n}+\gamma(n)}{n})^{n-1} \sim ne^{-(\log{n}+\gamma(n))} = e^{-\gamma(n)} \to \infty$.

I think this last step holds but it may depend on $\gamma$: in general I'm not sure for which functions $(1+\frac{f(n)}{n})^n \to e^{f(n)}$, I know this is true for the log term but maybe not if $\gamma$ grows very fast (though obviously it can't grow any faster than $1-\frac{\log{n}}{n}$ otherwise we would have $p>1$).

We can also calculate the second moment and get $\mathbb{E}(X^2)-\mathbb{E}(X)^2 \sim e^{-\gamma(n)}$ and deduce that with high probability there is an isolated vertex. Thus again, both probabilities are equal and we can take (e.g.) $c=1$.

The hard case is where $\gamma(n) \to k$: in this case we can reapply the same method to get $\mathbb{E}(X) \sim e^{-k}$, a constant. We can calculate again $\mathbb{E}(X^2) -\mathbb{E}(X)^2 \sim e^{-k}$, and use Chebyshev's inequality to calculate $\mathbb{P}(X=0) \leq e^{-k}/e^{-2k} = e^k$. If $k<0$, then this gives us an actual bound on the probability; otherwise we just get $\mathbb{P}(X=0) \leq 1$.

Supposing $k<0$ then; we can rewrite as $s:=\mathbb{P}(X>0)=\mathbb{P}$(isolated vertex)$\geq 1-e^k$, $d:=\mathbb{P}($disconnected) and using the fact $d =1- e^{-e^{-k}}$ and a little rearranging I think we get out the inequality $d \leq 1-\exp\left(\frac{1}{s-1}\right)$. We can then find a $c$ which works by applying the lower bound to $s$ in terms of $k$ then looking at the values of $c$ such that $cx \geq 1-\exp\left(\frac{1}{s-1}\right),\,x \in [1-e^k,1]$. However, this is only for fixed $k$! If we try and do this for every $k<0$ (i.e. every probability of this type) simultaneously, then we find that $c$ must be arbitrarily large. What's worse, this method doesn't work at all for $k \geq 0$ where we don't have a lower bound for $s$: in this case $s$ can be arbitrarily small and we can't pick a $c$ big enough to always work. So close and yet so far.

I am aware this question's length has spiralled out of control, so apologies for that - I know there's a good chance Math.SE is not going to provide me with an answer to this one. Nevertheless, it says add your working and this is what I managed to do! A proof which works for all slowly decreasing $\gamma$ or $\gamma \to k \in (-\infty,-\epsilon],$ any $\epsilon > 0$.

I have a strong suspicion this is not how I was meant to try and tackle the question, but tragically this is the best I could do so far. Thank you in advance to anyone who actually reads through all this!


Your Answer

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

Browse other questions tagged or ask your own question.