Proof that $t(n)=\frac{r}{n-1}$ is a threshold function in random G(n,p) graph

Question

I've been looking everywhere for a rigorous and detailed proof that $$t(n)=\frac{1}{n-1}$$ is a threshold function for the property that a single distinguished node in a random Erdos Reny graph has nonzero degree: $$A(N)=\{g|d_1(g)\geq 1\}$$ According to Jackson's definition we need to prove that $$PR[A(N)|p(n)] \rightarrow 1 \text{ if } p(n)/t(n) \rightarrow \infty $$ $$PR[A(N)|p(n)] \rightarrow 0 \text{ if } p(n)/t(n) \rightarrow 0 $$

Thanks!

Link to reference material https://www.coursera.org/learn/social-economic-networks/lecture/1nyN3/2-7-random-networks-thresholds-and-phase-transitions

Answer 1

Since each of $n-1$ possible edges out of the distinguished node is (independently) present with probability $p$, the distribution of its degree is a $\text{Binomial}(n-1,p)$ random variable.

So one way to proceed would be to analyze the behavior of $(1-p)^{n-1}$ - the probability that the degree is $0$ - as $n \to \infty$. In this case, that's not too terrible. But it goes against the spirit of random graphs; for harder problems, such methods will no longer work, because the exact probability of events is too hard to find.

Instead, here's a more typical approach. Let $\mathbf X$ be the degree of the distinguished node.

1. To show that $\Pr[\mathbf X \ge 1] \to 0$ as $n \to \infty$ if $p \ll \frac1{n-1}$, we can use the upper bound $\Pr[\mathbf X \ge 1] \le \mathbb E[\mathbf X]$. Here, the expected value of $\mathbb E[\mathbf X]$ is just $(n-1)p$, and $(n-1)p \to 0$ precisely when $p \ll \frac1{n-1}$. We are done by the squeeze theorem.
2. To show that $\Pr[\mathbf X \ge 1] \to 1$ as $n \to \infty$ if $p \gg \frac1{n-1}$, we can use the second moment method. A useful consequence of Chebyshev's inequality is that for a random variable $\mathbf X$ whose values are nonnegative integers, $\Pr[\mathbf X = 0] \le \frac{\text{Var}[\mathbf X]}{\mathbb E[\mathbf X^2]}$. In this case, the bound tells us that $$\Pr[\mathbf X = 0] \le \frac{(n-1)p(1-p)}{(n-1)p((n-1)p+1-p)} = \frac{1-p}{(n-1)p+1-p}.$$ If $p \gg \frac1{n-1}$, then $(n-1)p \to \infty$, so $\Pr[\mathbf X = 0] \to 0$ by the squeeze theorem.

(To compute quantities like $\mathbb E[\mathbf X^2]$, think of this random variable as counting ordered pairs of edges out of the distinguished node. There are $(n-1)(n-2)$ pairs $(e_1, e_2)$ which are present with probability $p^2$ and $n-1$ pairs $(e_1, e_1)$ present with probability $p$, so $\mathbb E[\mathbf X^2] = (n-1)(n-2)p^2 + (n-1)p$, which can be rewritten as $(n-1)p((n-1)p+1-p)$.)