1
$\begingroup$

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?

$\endgroup$
4
  • $\begingroup$ Can you use the central limit theorem to estimate the probability that a particular vertex has degree at least $(\log n)^{½}$? $\endgroup$ Commented 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 Erdos-Renyi graphs did not give you an answer. $\endgroup$
    – usul
    Commented 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$ Commented 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 Kfir
    Commented Nov 15, 2022 at 15:47

1 Answer 1

1
$\begingroup$

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}

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.