Connectivity of a graph in the Erdős–Rényi model

Question

In the lecture series on random graphs that I'm watching teacher has made the following statements: if the probability of a branch between any two vertexes to be present in a graph is this function of number of vertexes: $p(n) = c\frac {log(n)}{n}$, then there are 3 cases depending on the value of $c$:

1. if $c$ is > 1 then the probability that the graph is connected tends to 1 as $n \rightarrow \infty $
2. if $c$ is < 1 then the probability that the graph is connected tends to 0 as $n \rightarrow \infty $
3. if $c$ is = 1 then the probability that the graph is connected tends to $e^{-1}$ as $n \rightarrow \infty $

The 1st and 2nd ones have been proven, but the 3rd one hasn't due to its significantly higher difficulty in terms of means needed to carry out the proof. My question is where can I read about this proof and what are the prerequisites for understanding it?

Answer 1

Frieze and Karoński's Introduction to Random Graphs has already been cited in the comments as a book that explains this; it's one of many options you've got. So let me say a bit about what you'll need to understand the proof.

The first step to understanding this proof is knowing the story of the evolution of $\mathbb G_{n,p}$. The part of this story we care about is that as edge probability increases, larger components disappear first, until eventually all that's left is a few isolated vertices and an otherwise connected graph. When those isolated vertices join up with the rest of the graph, we're done.

So we should begin by proving that this is what's going on: that when $p = \frac{\log n}{n}$, the probability of having a $k$-vertex connected component tends to $0$ for $2 \le k \le \frac n2$. This should be very similar to how you proved connectivity for $p = c \frac{\log n}{n}$, $c>1$. The extra trick is that when you're looking at $k$-vertex connected components for small $k$, you can bound their expected number by $\binom nk {\color{red}{k^{k-2} p^{k-1}}} (1-p)^{k(n-k)}$. This adds a factor of $k^{k-2}$ for the number of possible spanning trees, and $p^{k-1}$ for the probability that the spanning tree is present. (For large $k$, nothing needs to change.)

To get the probability of $e^{-1}$, we should prove that the probability that there are no isolated vertices approaches $e^{-1}$: that's the remaining way to get a disconnected graph. The probability that a given vertex is isolated is $(1-p)^{n-1} \sim e^{-pn} \sim \frac1n$, and from here, we must do something fancy. You have options!

• Use inclusion-exclusion to analyze the probability of no isolated vertices; you should get something that resembles the sum $e^{-1} = \frac1{0!} - \frac1{1!} + \frac1{2!} - \frac1{3!} + \frac1{4!} - \dots$.
• Use the method of moments to prove that $\mathbf X$, the number of isolated vertices, is asymptotically Poisson. To do this, show that $\mathbb E\left[\binom{\mathbf X}{k}\right] \to \frac1{k!}$ for constant $k$, as $n \to \infty$. This value of $\frac1{k!}$ is what we'd get for a Poisson random variable with mean $1$, and this is enough to show that $\Pr[\mathbf X = 0] \to e^{-1}$: the probability that a Poisson random variable with mean $1$ is $0$.