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

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'$$?

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.

• Thank you so much for your detailed answer! If my understanding is correct, then "$S$ is independent" means that no two vertices in $S$ are adjacent? Alternatively, if I approach this problem by following the hint from the book, how should I define $d_i'$ so that they are independent (in the sense of probability)? Jul 26, 2022 at 10:07
• Yes! In graph theory an "independent set" is a set of vertices, no two of which are joined by an edge. Jul 26, 2022 at 12:58