2
$\begingroup$

I have this homework question: "Show that a ramdom graph with edge probability $p=\frac{10\log(n)}{n}$ almost certainly has no isolated vertices, while a random graph with edge probability $p=\frac{\log(n)}{10n}$ almost certainly has at least one isolated vertices."

For the first part of the problem, it seems trivial for small $n$, since $p=\frac{10\log(n)}{n}\ge1,$ so I guess we might as well assume $n$ is large enough to get $p<1$. Now, I would like to say that the probability any particular vertex is isolated is $$\left[1-\frac{10\log(n)}{n}\right]^{n-1},$$ since there is a $1-\frac{10\log(n)}{n}$ chance that a specific vertex fails to connect to another, and these $n-1$ events are independent. Is this logic correct? Furthermore, the expected number of isolated vertices should be $$n\left[1-\frac{10\log(n)}{n}\right]^{n-1},$$ as we are just summing the $n$ possible vertices times the probability that that vertex is isolated right? If so, then the expected value goes to zero as $n\to\infty$, which goes to show that the probability that there is at least one isolated vertex is $0$ by Markov's inequality Theorem.

On the other hand, for $p=\frac{\log(n)}{10n}$, we get that the expected value $$n\left[1-\frac{\log(n)}{10n}\right]^{n-1}$$ blows up as $n$ gets big, is this enough to say that there is almost certainly an isolated vertex in the graph?

Lastly, does anyone know a good beginner's resource for learning how to use the probabilistic method for graph theory exercises? I am struggling to gain intuition on solving these. Most of the info I find online tends to assume the reader is not an idiot, which I am. Thanks in advance!

$\endgroup$
1
  • 1
    $\begingroup$ You won't find a resource that makes probabilistic combinatorics easy, because probabilistic combinatorics is hard. I've seen it literally make grad students cry. You call this question a homework question, so you probably have an instructor with office hours; I suggest trying to get as much use out of both the instructor and their office hours as possible. $\endgroup$ Nov 1, 2017 at 3:03

1 Answer 1

3
$\begingroup$

The events "vertex $v$ is isolated" are not independent: if vertex $v_1$ isolated, then in particular it has no edge to $v_2$, making it a tiny bit more likely that vertex $v_2$ will be isolated.

That being said, you don't need independence to compute the expectation: it's still true that the expected number of isolated vertices is $n(1-p)^{n-1}$, even though the events are not independent.

You're correct that this expected value goes to $0$ in the first case, which shows that almost certainly no vertex is isolated...

...and you're also correct that this expected value diverges as $n \to \infty$ in the second case, but this does not imply that there are almost certainly isolated vertices. If we compute more precisely, the expected value is $(1+o(1))n^{0.9}$, but this sort of thing can happen for many reasons:

  • It could (and in fact does) reflect a situation in which there are $n^{0.9}$ isolated vertices almost all of the time.
  • But you haven't ruled out something like "with probability $n^{-0.1}$, there are $(1+o(1))n$ isolated vertices; the rest of the time, there are none".

That last one is an extreme example, but the point is that a large expected number of isolated vertices does not imply that isolated vertices almost always exist.

We deal with this in a way that's typical for calculations in random graphs:

  • To show that a random variable $X$ is almost always $0$, it's enough to show $\mathbb E[X] \to 0$ (that's your first case).
  • To show that a random variable $X$ is almost always large in the case where $\mathbb E[X]\to \infty$, show that $\text{Var}[X] = o(\mathbb E[X]^2)$ and use Chebyshev's inequality in the form $$\Pr[X=0] \le \frac{\text{Var}[X]}{\mathbb E[X]^2}.$$

In the second case of your problem, you should get $\text{Var}[X] \sim n^{0.9}$, which is much smaller than $E[X]^2 \sim n^{1.8}$, so everything goes through.

$\endgroup$
1
  • $\begingroup$ Ah I see, the textbook my class is using does not have an example (at least not in what we've covered thus far) dealing with the case when E(X) goes to infinity, so I was wondering about that. Thank you so much for this! $\endgroup$ Nov 1, 2017 at 3:11

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.