# Expected number of isolated vertices in a random graph.

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?

• Since ${n \choose 2} = n(n-1)/2$, you can expand it and cancel some factors and simplify a bit more, and perhaps that will be helpful to whatever you're trying to do next? IMHO the answer is perfectly good as it is (if this were e.g. a homework problem). ... Completely alternatively, I wonder if one can set up a recurrence in $m$, but I'm not sure. May 9, 2020 at 16:06
• A simple approximation is to consider the $G(n,p)$ graph model instead (choose each edge independently with probability $p=m/\binom{n}{2}$, instead of a uniform subset of $m$ edges). The resulting expression is a bit nicer. May 9, 2020 at 17:02

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.