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.
MathOverflow is a question and answer site for professional mathematicians. It only takes a minute to sign up.
Sign up to join this communityIf $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.
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<k-1)^k$, so $$\operatorname{Pr}(\text{celebrity}) = \sum \operatorname{Pr}(X=k)\operatorname{Pr}(X<k-1)^k.$$ 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}$.