Independence of Vertex Degrees in Erdős-Rényi Random Graph $G(n,p)$

Question

I am self-studying Chapter 8 (Random Graphs) of the book Foundations of Data Science. The example on page 250 tries to bound the probability of the existence of a vertex in $G(n,1/n)$ with degree $\Omega(\log n/\log\log n)$. I am having trouble with the last few lines:

But the degrees are not quite independent since when an edge is added to the graph it affects the degree of two vertices. This is a minor technical point, which one can get around.

How do I get around this technical point?

I also saw something similar in Exercise 2.4.4 of Vershynin's High-Dimensional Probability (which I am unable to solve):

Exercise 2.4.4 (Sparse graphs are not almost regular). Consider a random graph $G\sim G(n,p)$ with expected degrees $d=o(\log n)$. Show that with high probability, (say, $0.9$), $G$ has a vertex with degree $10d$.

Hint: The principal difficulty is that the degrees $d_i$ are not independent. To fix this, try to replace $d_i$ by some $d_i'$ that are independent. (Try to include not all vertices in the counting.) Then use Poisson approximation (2.9).

I found an answer in this post but I have some doubts about it:

• The answer says that with high probability, the degrees of the vertices in $V'$ are independent. Does it mean something like $\mathbb{P}(\mathbb{P}(AB)=\mathbb{P}(A)\mathbb{P}(B))\ge 1-\epsilon$? Why does it make sense?
• The answer seems to use approximation to Poisson$(d)$. But isn't $d$ changing with $n$? The Poisson Limit Theorem does not seem to apply.
• How does one get rid of the $o(1)$ term in Poisson approximation?

---

Update: Sameer Kailasa has provided a very nice solution to Exercise 2.4.4 using conditional probability (conditioned on a subset of vertices being an independent set). I wonder if there is an alternative solution that follows the hint of the book by defining some independent $d_i'$?

Answer 1

We consider the situation of the Exercise 2.4.4 from Vershynin. Take a small $\epsilon > 0$; since $d = o(\log(n))$, we have that $p < \epsilon \log(n)/n$ for all sufficiently large $n$.

For a fixed subset of $k$ vertices, the probability that there is no edge joining any two of them is $$(1 - p)^{\binom{k}{2}} > \left(1 - \frac{\epsilon \log(n)}{n} \right)^{k^2} \ge 1 - \frac{\epsilon \log(n) k^2}{n}$$ where we applied the Bernoulli inequality. Hence, for any $\delta > 0$, if we set $k = n^{1/2 - \delta}$, then as $n \to \infty$ the probability that any particular set of $k$ vertices is independent approaches $1$.

Thus, we can proceed as follows. Choose a particular set of $k$ vertices, and consider the event $E$ that none of them has degree equal to $10d$. We have

$$\mathbb{P}(E) \le \mathbb{P}(E \, | \, S \text{ is independent}) + \mathbb{P}(S \text{ is not independent})$$ By the argument above, the latter probability can be made arbitrarily small as $n \to \infty$. Thus, we must bound the former probability, which is computable due to the conditional independence; it is exactly $$\left(1 - \binom{n-k}{10d} p^{10d} (1-p)^{n-k-10d} \right)^{k}$$

Using the binomial coefficient lower bound $\binom{n}{k} \ge (n/k)^k$, we have now that $$\binom{n-k}{10d} p^{10d} (1-p)^{n-k-10d} \ge \left(\frac{(n-k)p}{10d} \right)^{10d} (1-p)^{n} $$ $$\ge \left( \frac{1}{20} \right)^{10\epsilon \log(n)} \left( 1 - \frac{\epsilon \log(n)}{n}\right)^n$$ since $n -k > (n-1)/2$ for large enough $n$. Crunching further with the numerical inequality $1 - x > e^{-2x}$ for $0 < x < 1/2$, we have for sufficiently large $n$ that $$\left( \frac{1}{20} \right)^{10\epsilon \log(n)} \left( 1 - \frac{\epsilon \log(n)}{n}\right)^n > e^{-10 \epsilon \log(20) \log(n)} e^{-2 \epsilon \log(n)} = n^{-C\epsilon}$$ for absolute constant $C$. Finally, we conclude that $$\mathbb{P}(E \, | \, S \text{ is independent}) \le \left(1 - \frac{1}{n^{C\epsilon}} \right)^{n^{1/2 - \delta}} < e^{-n^{1/2 - \delta - C\epsilon}}$$

Assuming $\delta$ and $\epsilon$ are chosen sufficiently small to ensure $1/2 - \delta - C \epsilon > 0$, the last inequality implies that the conditional probability vanishes as $n \to \infty$. We conclude that $\mathbb{P}(E) \to 0$ as $n \to \infty$, i.e. with high probability, there is a vertex of degree exactly $10d$ among our arbitrarily chosen set of $k$ vertices.

To sum up, the technical point mentioned in your question is that although vertices are not independent, with high probability a sufficiently small set of vertices (in this case $k = n^{1/2 - \delta}$) is independent. Then, conditioning on the very likely event enables us to finish the calculation.