Expected number of isolated vertices in a random graph.

Question

I'd like to find the expected number of isolated vertices in the random graph $G=(V,E)$, where $V=\{1,\ldots,n\}$, constructed choosing uniformly at random $m$ edges out of the $\binom{n}{2}$ possible edges. We have that, for a given vertex $v$, $$ \mathbb{P}(\text{\{$v$ is isolated\}})=\frac{\binom{\binom{n-1}{2}}{m}}{\binom{\binom{n}{2}}{m}}, $$ and from here, defining $X$ as the (random) number of isolated vertices, we could work $\mathbb{E}(X)$ out writing $X$ as $\sum_{v\in V}1_{\text{\{$v$ is isolated}\}}$ and hence $$ \mathbb{E}(X)=\mathbb{E}\Bigg(\sum_{v\in V}1_{\text{\{$v$ is isolated}\}}\Bigg)=\sum_{v\in V}\mathbb{E}(1_{\text{\{$v$ is isolated}\}})=\sum_{v\in V}\mathbb{P}({\text{\{$v$ is isolated}\}})=n\cdot\frac{\binom{\binom{n-1}{2}}{m}}{\binom{\binom{n}{2}}{m}}. $$ The problem is that I don't exactly know how to work $\frac{\binom{\binom{n-1}{2}}{m}}{\binom{\binom{n}{2}}{m}}$ out. Is there a nicer expression for it?

Answer 1

For an exact expression, this is basically as simplified as you get. You can simplify it a bit using falling powers. Let $(n)_k$ denote the product $n(n-1)(n-2) \dotsm (n-k+1)$. Then $\binom nk = \frac{(n)_k}{k!}$. So in our case, we have $$ \frac{\binom{\binom{n-1}{2}}{m}}{\binom{\binom{n}{2}}{m}} = \frac{\binom{N-n+1}{m}}{\binom Nm} = \frac{(N-n+1)_m/m!}{(N)_m/m!} = \frac{(N-n+1)_m}{(N)_m}. $$ Here, I write $N$ for $\binom n2$.

When $m > n-1$, if we were actually calculating the expression above, it would be simpler to cancel factors on top and bottom to get $$ \frac{(N-n+1)_m}{(N)_m} = \frac{(N-m)_{n-1}}{(N)_{n-1}}. $$ But that's not a huge change.

People do also think about asymptotic approximations of this: we have $$ \frac{(N-n+1)_m}{(N)_m} \approx \frac{(N-n+1)^m}{N^m} = \left(1 - \frac{n-1}{N}\right)^m = \left(1 - \frac 2n\right)^m \approx e^{-2m/n}. $$ When $m$ is relatively small, we can show that this approximation is pretty close to the original as $n \to \infty$, and of course understanding the quantity $n e^{-2m/n}$ as an approximation to the number of isolated vertices is much easier. For all values of $n$ and $m$, the $\approx$ approximations above are also $\le$ upper bounds, so that $n e^{-2m/n}$ is always an upper bound on the expected number of isolated vertices.