Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.