# Expected maximum degree Erdős–Rényi graph

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?

• 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. – 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$.