# Vertex degree on random graphs

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?

• Can you use the central limit theorem to estimate the probability that a particular vertex has degree at least $(\log n)^{½}$? Commented Nov 13, 2022 at 23:35
• It would help motivate to say where the question comes from, and why the large amount of existing research on Erdos-Renyi graphs did not give you an answer.
– usul
Commented Nov 14, 2022 at 3:32
• The distribution of one degree is binomial, which in this case is very close to a Poisson distribution with mean $d$. Moreover, the degrees of two vertices are almost independent. The second moment method will give you what you want. This sort of thing is well worked out, probably it is a special case of something in Chapter 3 of Bollobás' book "Random Graphs". Commented Nov 14, 2022 at 13:50
• I tried to do it and got confused.. I would like instructions on how to use the second moment here ? Commented Nov 15, 2022 at 15:47

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}