# Probability of a vertex being a "degree-celebrity" in a random graph

If $$G(n,p)$$ is a random graph of the Erdös-Rényi model,
what is the probability that $$\mathrm{deg}(v)\gt\mathrm{deg}(u)\ \forall u\in\mathrm{adj}(v)$$

Please feel free to relate answers to other models of random graphs.

## 1 Answer

Calculating analogously to the friendship paradox:

In the large $$N$$ limit with fixed average degree $$d=np$$ the degree of each node is distributed as Poisson with mean $$d$$ while each neighbor is Poisson with mean $$d+1$$. So we condition on $$k$$ and compute the probability that all the neighbors have degree less than $$k$$. Let $$X$$ be Poisson with mean $$d$$; then $$\operatorname{Pr}(\text{celebrity}|\deg=k) = \operatorname{Pr}(X, so $$\operatorname{Pr}(\text{celebrity}) = \sum \operatorname{Pr}(X=k)\operatorname{Pr}(X Call this $$r(d)$$.

Numerically, $$r(1)=.063$$, $$r(2)=.065$$, $$r(3)=.05$$, $$r(5)=.041$$, $$r(10)=.002$$, $$r(20)=4 \times 10^{-10}$$.