Bounding the Degrees of Very Sparse Graphs (Vershynin 2.4.3)

38 Views Asked by At

I think I might've solved Exercise 2.4.3 in Vershynin's High Dimensional Probability, although I am suspicious of my solution.

The problem:

Consider a random graph $G\sim G(n, p)$ with expected degrees $d=O(1)$. Show that with high probability (say, 0.9), all the vertices of $G$ have degree $$O\left(\frac{\log n}{\log\log n}\right).$$

My solution: Let $D>0$ be such that $d \leq D$ for all $n$. Let $C>0$ (to be determined later), and then by a union bound and Chernoff's inequality, $$P\left(\text{any vertex has degree at least } C\frac{\log n}{\log\log n}\right) \leq nP\left(d_1 \geq C\frac{\log n}{\log\log n}\right) \leq ne^{-d}\left(\frac{ed}{C} \frac{\log\log n}{\log n}\right)^{C\frac{\log n}{\log\log n}}.$$ For convenience, let $\alpha = \frac{eD}{C}$. Because $0\leq d \leq D$, we can continue the above inequalities to get $$\cdots \leq n\left(\alpha\frac{\log\log n}{\log n}\right)^{C\frac{\log n}{\log\log n}}= n^{1-C + \frac{C\log\log\log n}{\log\log n} + \frac{C\log\alpha}{\log\log n}}.$$ As $n\to\infty$, the final expression goes to 0 so long as $C>1$. Therefore, if we let $C>1$, then for $n$ sufficiently large, all vertices of $G$ have degree at most $\frac{C\log n}{\log\log n}$ with probability at least 0.9. QED.

Here's why I'm slightly suspicious of this answer: I would've expected the value of $C$ for the argument to go through to depend on $D$. But here we see that one choice of $C$ works.

Thanks for the help!