Vertex degree on random graphs

Question

Let $p = d/n$ with $d$ constant. How do I prove that, with high probability, $G_{n,p}$ contains a vertex of degree at least $(\log n)^{1/2}$, where $G_{n,p}$ is a graph with $n$ vertices and the number of edges is a binomial random variable with the parameters?

Answer 1

Just an amateur answer, I would assume there's a paper or known approach out there from experts.

I would partition the vertices into equal sets $U,V$ and delete edges to make it a bipartite graph. It suffices to show that there exists a vertex in $U$ with enough edges after the deletions.

Now the degrees of vertices in $U$ are independent, so the probability they all have degree less than some given $t$ is the product of the probabilities. And we can bound \begin{align} \Pr[\text{degree}(v) < t] &= 1 -\Pr[\text{degree}(v) \geq t] \\ &\leq 1 - \Pr[\text{degree}(v) = t]. \end{align} (You could try for a more sophisticated bound, but I don't think it will help much when the mean degree is a constant $d$ and $t = \omega(1)$.) Then, \begin{align} \Pr[\text{degree}(v) = t] &= {n/2 \choose t} p^t (1-p)^{n/2-t} \\ &\geq \left(\frac{n}{2t}\right)^t p^t (1-p)^{n/2-t} \\ &= \left( \frac{d}{2t} \right)^t (1-p)^{n/2-t} \\ &\approx \left( \frac{d}{2t} \right)^t e^{-np/2} \\ &= \left( \frac{d}{2t} \right)^t e^{-d/2} . \end{align} (This is essentially the Poisson approximation; there may be better ways, and note you'll have to rigorously handle the $\approx$ step.) For $t = o(\ln(n)/\ln(\ln(n)))$, I believe $(2t/d)^t = o(n)$. It must be true for $t = \sqrt{\ln(n)}$. So \begin{align} &\Pr[\text{all vertices in $U$ have degree $< t$}] \\ &\leq (1 - \Pr[\text{degree}(v) = t])^{n/2} \\ &\approx (1 - (d/(2t))^t e^{-d/2})^{n/2} \\ &\leq \exp\left( - \frac{n (d/(2t))^t e^{-d/2}}{2} \right) \\ &= \exp\left( - \omega(1) \right). \end{align}