1
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – antkam
    May 9, 2020 at 16:06
  • $\begingroup$ 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. $\endgroup$
    – Clement C.
    May 9, 2020 at 17:02

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.