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?

$\begingroup$ Can you use the central limit theorem to estimate the probability that a particular vertex has degree at least $(\log n)^{½}$? $\endgroup$– Andreas BlassCommented Nov 13, 2022 at 23:35

$\begingroup$ It would help motivate to say where the question comes from, and why the large amount of existing research on ErdosRenyi graphs did not give you an answer. $\endgroup$– usulCommented Nov 14, 2022 at 3:32

1$\begingroup$ 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". $\endgroup$– Brendan McKayCommented Nov 14, 2022 at 13:50

$\begingroup$ I tried to do it and got confused.. I would like instructions on how to use the second moment here ? $\endgroup$– Nir KfirCommented Nov 15, 2022 at 15:47
1 Answer
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 (1p)^{n/2t} \\ &\geq \left(\frac{n}{2t}\right)^t p^t (1p)^{n/2t} \\ &= \left( \frac{d}{2t} \right)^t (1p)^{n/2t} \\ &\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}