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'|$?
Best 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 \leq C_1\log n$, Thanks Jiayao)
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.