1
$\begingroup$

For a random graph G(n,p), I can understand how to calculate the E(X) where X is the number of isolated vertices. However, in the case of fixed N edges (N = cn), I am not sure how to proceed in the same calculation of E(X). I don't think finding p = N/$ \binom n2$ would work since that would only give number of edges around N, not exactly N. What I considered was proceeding by find the probability that a vertex has at least one edge, which I think should be $\frac{n}{n(n-1)/2} = \frac{2}{n-1}$. However this looks wrong to me since this would give >1 probability when n=2. I am not sure how to go ahead, any hint would be very helpful.

$\endgroup$
2
$\begingroup$

You have $n$ points and $m$ edges ($0<m<\binom{n}{2}$); and all possible graphs of that kind can form with no bias (equal probability).

There are $\dbinom{\binom{n}{2}}{m}$ possible graphs that can form.

For any particular node, #$k$, there are $\dbinom{\binom{n-1}{2}}{m}$ graphs that can form that isolate node.

Eg : $n=4$ $M=2$, there are $\binom{6}{2}$, or $15$ possible graphs, and $3$ of these isolate node #$2$

Take it from there...

$\endgroup$
3
$\begingroup$

For each vertex $v$, define the random variable $X_v$ that is 1 if $v$ has degree $0$ and $0$ otherwise.

Then, $\mathbb{E}(X_v) = \mathbb{P}(X_v = 1)$, where the probability is the fraction of random selections of $k$ edges that leave $v$ isolated, over all possible selections of $k$ edges.

$$\mathbb{P}(X_v = 1) = \frac{\binom{\frac{n(n-1)}{2}-(n-1)}{k}}{\binom{\frac{n(n-1)}{2}}{k}} = \frac{\binom{\frac{(n-1)(n-2)}{2}}{k}}{\binom{\frac{n(n-1)}{2}}{k}}$$

Then, by linearity of expectation, the number of isolated vertices is $n\mathbb{E}(X_v)$.

Note that this does make sense for small examples. For instance if $n = 2, k= 1$, we have an expectation of $2\frac{\binom{0}{1}}{\binom{1}{1}} = 0$ isolated vertices, while for $n = 2, k=0$, the expectation is $2\frac{\binom{0}{0}}{\binom{1}{0}} = 2$. If $n = 3, k=1$, we get an expectation of one isolated vertex, etc.

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