# Given a random graph $G_{n,p}$, how to get the expectation of number of components with $k$ vertices and $k$ edges?

A random graph $G_{n,p}$ is a graph with $n$ vertices, but every edge exists independently with probability $p$.

If we know

$$np = c, 0 < c < 1$$

how to get the expectation of number of components with $k$ vertices and $k$ edges when $n$ goes to infinity, where $k$ is constant less than $n$.

(In Erdos' classical paper "On the evolution of random graph", he actually gave a result of the problem, but without details of proof. So I have trouble understanding how he reached the conclusion.)

-

Let $G_k$ be the number of connected graphs with $k$ edges, on $k$ labeled vertices. The probability that any particular $k$ vertices will form a component of the type that interests you is $$G_k p^k (1-p)^{\binom{k}{2} - k + k(n-k)}.$$ So your expectation is $$G_k p^k (1-p)^{\binom{k}{2} - k + k(n-k)} \binom{n}{k}.$$ If $p=c/n$, then this is $$G_k (c/n)^k (1-c/n)^{kn + \mbox{constant}} \frac{n^k}{k!} (\mbox{terms going to 1}) \sim G_k c^k e^{-ck} / k!$$

There is no closed formula for $G_k$; the sequence is A057500 in Sloane. See Joriki's answer for a reasonably nice formula for $G_k$.

I'm not sure that this is what you wanted to ask.

-
I'd be interested in your view on the discrepancy discussed in my answer. – joriki Oct 12 '11 at 21:16
David, this has come up again in this question (interestingly in the practical context of writing a puzzle for a game) -- do you have any thoughts on the discrepancy discussed in my answer? – joriki Dec 25 '11 at 0:29

I thought you were trying to understand the expression

$$\frac{(2c\mathrm e^{-2c})^k}{k!}\left(1+k+\frac{k^2}{2!}+\dotso+\frac{k^{k-3}}{(k-3)!}\right)$$

in Section 2, Phase 2 of the paper. Now that you've accepted an answer that doesn't refer to that, I'm not sure, but I'll write out my answer anyway.

First, note the scenario you describe is not the one investigated in the paper; in fact it's the one that's mentioned at the end of the footnote on the first page. In your scenario, the probability for each edge to exist is independent of the probabilities for all other edges. In the scenario in the paper, a graph containing a fixed number $N$ of edges is chosen at random. In this case, since the total number of edges is fixed, the existence of an edge makes the existence of other edges less likely.

However, the two scenarios are of course closely related, and one would expect the difference to vanish with $n\to\infty$, much as the difference between the microcanonical ensemble and the canonical ensemble becomes irrelevant in the thermodynamic limit.

So let's assume your scenario. Somewhat confusingly, you introduced a parameter $c$ that's twice the corresponding parameter in the paper: Whereas the paper assumes $N\sim cn$, you assume $p\sim c/n$, and since in the limit $n\to\infty$ we'd expect $p\sim N/\binom n2\sim2N/n^2$, there's a factor of $2$. I'll use $c$ as you defined it, but this needs to be replaced by $2c$ to get the expression given in the paper.

David has already shown that the expected number of components with $k$ vertices and $k$ edges is $G_kc^k\mathrm e^{-ck}/k!$, so it only remains to determine the number $G_k$ of connected graphs with $k$ edges on $k$ labeled vertices. This can be done using a generalized form of Prüfer sequences.

A connected graph with $k$ vertices and $k-1$ edges is a tree, so a connected graph with $k$ vertices and $k$ edges has exactly one cycle. Let $m$ be the number of edges in that cycle. Now define a generalized Prüfer sequence as follows: As for trees, in each step remove the vertex with degree $1$ with the smallest label. Whereas for a tree this process ends with just $2$ vertices left, in the present case it ends with just the cycle left. All labels in the sequence except for the last one can be any of the $k$ labels; the last one has to be one of the $m$ labels of the vertices in the cycle. Thus there are $mk^{k-m-1}$ possible Prüfer sequences, and as in the tree case these are in bijection with the possible extensions of a given $m$-cycle. There are $\binom km$ ways to choose the $m$ vertices in the cycle, and $(m-1)!/2$ ways to arrange them in a cycle ($m!$ permutations, of which $m$ are equivalent via a cyclical shift and $2$ are equivalent via inversion). Putting it all together and summing over $m$ from $3$ to $k$ to account for all possible numbers of vertices in the cycle, we have

$$G_k=\sum_{m=3}^k\binom km\frac{(m-1)!}2mk^{k-m-1}=\frac{(k-1)!}2\sum_{m=3}^k\frac{k^{k-m}}{(k-m)!}\;.$$

Comparing with the expression in the paper, in which the sum in parentheses should be $G_k$, there's an extra factor of $(k-1)!/2$. The result appears to be correct, though, as you can check by comparing with the OEIS page David linked to, or by counting the cases $k=3$ and $k=4$ by hand. It seems unlikely that the discrepancy is due to the differing scenarios discussed above, which might manifest in more subtle effects but not in such a large factor; this is confirmed by the result $(2c)^k/(2k)$ for the expected number of $k$-cycles a few lines further up, which takes the factor $(k-1)!/2$ into account and coincides with what one would expect in your scenario. So I can't see any explanation for the discrepancy; it seems that the factor $(k-1)!/2$ may have been omitted by accident in the paper.

-
A connected graph with $k$ vertices and $k$ edges need not be a cycle. – Chris Eagle Oct 8 '11 at 23:51
@Chris: You're right of course; I've now posted a corrected answer. – joriki Oct 12 '11 at 21:03