1
$\begingroup$

I'm taking a course which follows the book:
High-Dimensional Probability by Roman Vershynin.

There is an exercise (2.4.4) in the book which I have trouble with:
Consider a random graph $G \sim G(n,p)$ with expected degrees $d=o(\log n)$. Show that with high probability (say 0.9), $G$ has a vertex with degree $10d$.

To solve this I want to take a subset of vertices $V' \subset V$ s.t. each two vertices in $V'$ are not neighbors in the graph, so their degrees are independent. Then use Poisson approximation.
But I think that this way the expected degree of the vertices in this group is no longer $d$, and I cant figure out what can I say about $|V'|$?

$\endgroup$
2
$\begingroup$

Self answering for future reference.

We've solved it by taking $V' \subset V$ randomly of size $n^\frac{1}{3}$,
Since $d=o(\log n)$, $p=o(\frac{\log n}{n})$.
The expected number of edges between vertices in $V'$ is bounded by $n^\frac{2}{3}*p=o(\frac{\log n}{n^\frac{1}{3}})$ so with high probability, there are no edges between vertices in $V'$, therefore their degrees are independent.
Now since the degree of each vertex is the sum of Bernoulli Random variables with small probability, we'll use Poisson approximation,

$P(\exists i\leq n \, | \, d'_i = 10d) = 1 - P(\forall i\leq n \, | \, d'_i \neq 10d) = 1 - P(d'_i \neq 10d)^n = 1 - (1 - P(d'_i = 10d))^n$

$P(d'_i = 10d) = \frac{1}{\sqrt{2\pi 10d}}e^{-d}\frac{ed}{10d}^{10d} \geq ... \geq n^{-c}$
(by using $d \geq C_1\log n$)
Which c is a constant that depends on $C_1$, which can be small as we like (since it's small o).

Now,
$1 - (1 - P(d'_i = 10d))^n \geq 1 - (1 - n^{-c})^n \geq 1 - e^{-n^{\frac{1}{3}}/n^c} = 1 - e^{-n^{\frac{1}{3}-c}}$
Now we can choose c as we like to get the desired lower bound on the probability.

$\endgroup$
  • 2
    $\begingroup$ Your answer works fine, but I want to mention that we don't need to find an independent set $V'$. You can choose any $V'$ of reasonable size and simply say that for every $v \in V'$, the number of neighbors $v$ has outside $V'$ is binomial, and these binomial variables are independent. Then argue that some $v \in V'$ has at least $10d$ neighbors outside $V'$, and therefore has degree at least $10d$. $\endgroup$ – Misha Lavrov Mar 8 at 15:25
  • 1
    $\begingroup$ The question asks one with exactly 10d, I don't know how much it'll affect your answer, but it is interesting to look at it that way as well! $\endgroup$ – shahaf finder Mar 8 at 17:33
  • 2
    $\begingroup$ Exactly $10d$? Huh. Well, we could first look at the degrees inside $V'$, and then that sets a target (which is at most $10d$) for the number of neighbors we want to find outside $V'$ for each vertex. So it still works out. $\endgroup$ – Misha Lavrov Mar 8 at 17:44
  • 1
    $\begingroup$ Ok I understand, so it's another option, thanks! $\endgroup$ – shahaf finder Mar 9 at 18:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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