# Sparse random graph property

I'm taking a course which follows the book:
High-Dimensional Probability by Roman Vershynin.

There is an exercise (2.4.4) in the book which I have trouble with:
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$$.

To solve this I want to take a subset of vertices $$V' \subset V$$ s.t. each two vertices in $$V'$$ are not neighbors in the graph, so their degrees are independent. Then use Poisson approximation.
But I think that this way the expected degree of the vertices in this group is no longer $$d$$, and I cant figure out what can I say about $$|V'|$$?

## 1 Answer

Self answering for future reference.

We've solved it by taking $$V' \subset V$$ randomly of size $$n^\frac{1}{3}$$,
Since $$d=o(\log n)$$, $$p=o(\frac{\log n}{n})$$.
The expected number of edges between vertices in $$V'$$ is bounded by $$n^\frac{2}{3}*p=o(\frac{\log n}{n^\frac{1}{3}})$$ so with high probability, there are no edges between vertices in $$V'$$, therefore their degrees are independent.
Now since the degree of each vertex is the sum of Bernoulli Random variables with small probability, we'll use Poisson approximation,

$$P(\exists i\leq n \, | \, d'_i = 10d) = 1 - P(\forall i\leq n \, | \, d'_i \neq 10d) = 1 - P(d'_i \neq 10d)^n = 1 - (1 - P(d'_i = 10d))^n$$

$$P(d'_i = 10d) = \frac{1}{\sqrt{2\pi 10d}}e^{-d}\frac{ed}{10d}^{10d} \geq ... \geq n^{-c}$$
(by using $$d \geq C_1\log n$$)
Which c is a constant that depends on $$C_1$$, which can be small as we like (since it's small o).

Now,
$$1 - (1 - P(d'_i = 10d))^n \geq 1 - (1 - n^{-c})^n \geq 1 - e^{-n^{\frac{1}{3}}/n^c} = 1 - e^{-n^{\frac{1}{3}-c}}$$
Now we can choose c as we like to get the desired lower bound on the probability.

• Your answer works fine, but I want to mention that we don't need to find an independent set $V'$. You can choose any $V'$ of reasonable size and simply say that for every $v \in V'$, the number of neighbors $v$ has outside $V'$ is binomial, and these binomial variables are independent. Then argue that some $v \in V'$ has at least $10d$ neighbors outside $V'$, and therefore has degree at least $10d$. – Misha Lavrov Mar 8 at 15:25
• The question asks one with exactly 10d, I don't know how much it'll affect your answer, but it is interesting to look at it that way as well! – shahaf finder Mar 8 at 17:33
• Exactly $10d$? Huh. Well, we could first look at the degrees inside $V'$, and then that sets a target (which is at most $10d$) for the number of neighbors we want to find outside $V'$ for each vertex. So it still works out. – Misha Lavrov Mar 8 at 17:44
• Ok I understand, so it's another option, thanks! – shahaf finder Mar 9 at 18:11