6
$\begingroup$

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.

$\endgroup$
2
  • $\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, 2015 at 13:53
  • $\begingroup$ Your argument is sound if $p$ is not too small, but for sparse graphs, $p=c/(N-1)$, the degree is asymptotically Poisson with parameter $c$, while the max degree over $n$ vertices will obviously diverge. Also, the question asks for the expectation. $\endgroup$
    – Matija
    Feb 1, 2023 at 6:11

1 Answer 1

Reset to default
4
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .