Consider an Erdős–Rényi random graph $\mathrm{ER}(N,p)$, where $N$ is the number of nodes and $p$ the probability of placing an edge between each distinct pair of nodes.

I'm interested in finding the expected maximum degree of $\mathrm{ER}(N,p)$ as a function of $N$ and $p$. Do you know if such a result exists? In case of positive answer, can you provide me a reference in which the problem is addressed?

Thanks in advance for all your help.

  • $\begingroup$ I believe you can do more than that. Once the degree of each vertex follows a binomial distribution of parameters $N-1$ and $p$, via Chernoff bounds you can assure that every vertex is close to his expected value. Then, the maximum degree will be close of $(N-1)p$ with high probability. $\endgroup$ – Rodrigo Ribeiro Jul 26 '15 at 13:53

According to the paper titled "The Maximum Degree of a Random Graph" by Oliver Riordan and Alex Selby, given $b \geq 0$, the probability that the maximum degree of an Erdos--Renyi random graph $ER(N,p)$ is at most $Np+b\sqrt{Npq}$ is $\left(c+o(1)\right)^N$. Here, $q=1-p$ and $c=c(b)$ is the root of a certain equation. In particular, for $b=0$, $c=c(0)=0.6102\ldots$.


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.