I am trying to prove the following statement:
Consider a random graph $G \sim G(n, p)$ with expected degrees $d = O(1)$. Show that with high probability, (say, $0.9$), $G$ has a vertex with degree $$ \Omega\left( \frac{\log{n}}{\log{\log{n}}} \right). $$
This exercise appears in the application of Chernoff's inequality chapter from High-Dimensional Probability by Roman Vershynin.
Chernoff's Bound for upper tail: Let $X_i$ be independent Bernoulli r.v. with parameter $p_i$. Consider the sum $S_n = \sum_{i= 1} ^N X_i$ and $\mu = \mathbb{E}S_N$. Then for any $t > \mu$, we have $$ \mathbb{P}\{ S_N \geq t \} \leq e^{-\mu}\left( \frac{e\mu}{t} \right)^t. $$
Chernoff's Bound for lower tail: Let $X_i$ be independent Bernoulli r.v. with parameter $p_i$. Consider the sum $S_n = \sum_{i= 1} ^N X_i$ and $\mu = \mathbb{E}S_N$. Then for any $t < \mu$, we have $$ \mathbb{P}\{ S_N \leq t \} \leq e^{-\mu}\left( \frac{e\mu}{t} \right)^t. $$
Reverse Chernoff Bound: If $S_N$ is a Binomial r.v. with mean $\mu$, then $$ \mathbb{P}\{ S_N \geq t \} \geq e^{-\mu}\left( \frac{\mu}{t} \right)^t, \ \ \ \forall t \geq \mu. $$
My Attempt: We wish to show there exists some $C > 0$ such that $$ \mathbb{P}\{ \exists i \leq n: d_i \geq C\frac{\log{n}}{\log{\log{n}}} \} \geq 0.9. $$ Since the graph is very sparse, we can assume with high probability that some subgraph has independent degrees. Therefore, the question is equivalent to showing $$ \mathbb{P}\{ \forall i \leq n: d_i < C\frac{\log{n}}{\log{\log{n}}} \} = \prod_{i = 1} ^n \mathbb{P}\{ d_i < C\frac{\log{n}}{\log{\log{n}}} \} \leq 0.1. $$ This is really where I got stuck and can't seem to unstuck myself from. I want to use the Chernoff's bound to somehow bound this product, but since $n$ can be large, the Chernoff lower bound doesn't necessarily apply here. It is then natural to me to use the reverse Chernoff bound:
$$ \mathbb{P}\bigcup_{i = 1} ^n \{ d_i < C\frac{\log{n}}{\log{\log{n}}} \} = \prod_{i = 1} ^n (1 - \mathbb{P}\{ d_i \geq C\frac{\log{n}}{\log{\log{n}}} \}). $$ In particular, if we can show $(1 - \mathbb{P}\{ d_i \geq C\frac{\log{n}}{\log{\log{n}}} \}) > 0$ using the reverse Chernoff bound, then the result will be true for large enough $n$. This prompts me to do the following estimate:
\begin{align*} \mathbb{P}\{ d_i \geq C \frac{\log{n}}{\log{\log{n}}} \} \geq e^{-d}\left( \frac{d}{C\frac{\log{n}}{\log{\log{n}}}} \right)^{C\frac{\log{n}}{\log{\log{n}}}}. \end{align*}
But I am not sure how one can show this is greater than $0$ when $n \to \infty$.
Any suggestions?
First, regarding independence.
We cannot "assume with high probability that some subgraph has independent degrees". As soon as you look for a subgraph which has any particular property, you reveal the edges you inspected in doing so, and then you can no longer consider the degrees of those vertices to be random.
One easy way to get independence is to separate the vertices into sets of size $n/2$ (without looking at the edges between them!), and look at the bipartite subgraph consisting only of the edges between the two sets. In this bipartite subgraph, the degrees of vertices in one set are independent random variables.
While I'm correcting the attempt, let me also correct the problem. It is impossible to prove anything assuming $d = O(1)$, because $\frac1{n^2}$ is also $O(1)$, and a graph with expected degree $\frac1{n^2}$ probably doesn't have any edges. We must assume $d = \Theta(1)$. Actually, for the argument below, having an inequality like $\frac1{\log\log n} \le d \le \frac12 \log n$ for all sufficiently large $n$ would suffice. (Also, by monotonicity, the claim holds even when $d$ is higher.)
In the bipartite subgraph, the degree sequence of one set of vertices is $n/2$ independent random variables with the $\text{Binomial}(n/2, d/(n-1))$ distribution. The probability that one of these vertices has degree $k$ is $$\binom{n/2}{k} \left(\frac{d}{n-1}\right)^k \left(1 - \frac d{n-1}\right)^{n/2-k} \ge \left(\frac{n}{2k}\right)^k \cdot \frac{d^k}{n^k} \cdot e^{-d} = e^{-d} \left(\frac{d}{2k}\right)^k.$$ (Bounding the third term is a little bit tricky; $(1 - \frac1x)^{x-1} \ge e^{-1}$ for all $x\ge 1$, so $(1-\frac d{n-1})^{\frac{n-d-1}{d}} \ge e^{-1}$, and we are fine as long as $n/2-k < n-d-1$, which is true for sufficiently large $n$.)
Set $k = \frac{\log n}{3\log\log n}$. First of all, for sufficiently large $n$, we have $k < \frac{d}{2}\log n$, so $\frac{d}{2k} > \frac1{\log n}$. This means that the probability above is at least $$e^{-d} (\log n)^{-k} = e^{-d -k \log \log n} = e^{-d - \log n/3} = e^{-d} n^{-1/3},$$ which is not too shabby.
Let $q$ be the probability that a given vertex on the first side of the bipartite subgraph has degree $k$ (we've just proven that $q \ge e^{-d} n^{-1/3}$). For different vertices on the first side, the events of having degree $k$ in the bipartite subgraph are independent (they look at disjoint sets of edges). Therefore the number of vertices with degree $k$ is also a Binomial random variable: it is $X\sim \text{Binomial}(n/2, q)$.
$X$ has mean $nq/2$ and variance $nq(1-q)/2$, so by Chebyshev's inequality, the probability that $X=0$ is at most $\text{Var}[X]/\mathbb E[X]^2 = 2(1-q)/(nq) \le 2/(nq)$. In our case, $2/(nq) \le 2e^d/n^{2/3}$, which goes to $0$ as $n \to \infty$, so with high probability, $X>0$ and a vertex with degree $\frac{\log n}{3\log\log n}$ can be found.