3
$\begingroup$

Let $G$ be a graph on $n$ vertices on which we impose that the average degree is a constant $d$. Is it true that as $n \to \infty$ the degree of each node will be a Poisson-distributed random variable? I heard this claim in passing, saw no proof and I might misremember a crucial detail, so if any graph theorist knows of any claim that sounds similar, I would be very grateful.

$\endgroup$
5
  • 1
    $\begingroup$ Is that where you saw it? jsums.edu/nmeghanathan/files/2015/08/… $\endgroup$
    – markvs
    Commented Dec 9, 2021 at 20:24
  • $\begingroup$ No, I literally heard someone say it, but that is indeed the claim. Do you know where I can find an actual proof? @markvs $\endgroup$
    – Karl
    Commented Dec 9, 2021 at 20:29
  • $\begingroup$ I do not know but if I needed it, I would send a message to Dr. Natarajan Meghanathan. $\endgroup$
    – markvs
    Commented Dec 9, 2021 at 20:31
  • $\begingroup$ So to clarify, $G$ is not just a graph with average degree $d$, but rather a random graph uniformly picked among such graphs? $\endgroup$ Commented Dec 9, 2021 at 20:36
  • $\begingroup$ I guess you are right @HagenvonEitzen, it is a sparse network with average degree $d<<$ number of nodes $\endgroup$
    – Karl
    Commented Dec 9, 2021 at 20:45

1 Answer 1

2
$\begingroup$

Suppose $G$ is chosen by taking $n$ vertices $v_1, \dots, v_n$ and adding each possible edge $v_i v_j$ independently with probability $\frac{d}{n-1}$. Then for each $v_i$, $\deg(v_i)$ has the $\text{Binomial}(n, \frac{d}{n-1})$ distribution.

This distribution has expected value $d$ (so we get the average degree we wanted), and converges to $\text{Poisson}(d)$ as $n \to \infty$.

The content of this statement is that $$ \lim_{n \to \infty} \binom nk \left(\frac d{n-1}\right)^k \left(1 - \frac{d}{n-1}\right)^{n-1-k} = e^{-d} \frac{d^k}{k!} $$ for each constant $k$. This is true because:

  • $\binom nk \sim \frac{n^k}{k!}$ as $n \to \infty$.
  • $\left(\frac d{n-1}\right)^k \sim \frac{d^k}{n^k}$ as $n \to \infty$, which cancels with the previous factor to get $\frac{d^k}{k!}$.
  • $\left(1 - \frac{d}{n-1}\right)^{n-1-k} \sim \left(1 - \frac d{n-1}\right)^{n-1}$ as $n\to \infty$.
  • $\lim_{n \to \infty} \left(1 - \frac d{n-1}\right)^{n-1} = \lim_{n \to \infty} \left(1 - \frac d n\right)^n$ is exactly the limit definition of $e^{-d}$.
$\endgroup$

You must log in to answer this question.

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