Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I'm reading through my notes on the evolution of random graphs and have come unstuck trying to figure out the meaning of a probabilistic term which appears, and was hoping you could help - it's not very complex, I don't think.

I'm working in the space of random graphs $G_{n,p}$; graphs on $n$ vertices with all edges having (independent) probability $p$ of existing. I'm in the final leg of a multi-part proof, and for this final part I want to show that the "number of vertices on tree components" is given by a random number satisfying a certain condition which I don't think needs specifying here, though I can do if it will help. We've specified $p = \frac{\gamma \log{n}}{n}$, where $\gamma$ is some number between $\frac{1}{k+1},\,2$ (and $k \geq 1$ is some value needed elsewhere in the proof).

So, the line I can't understand is as follows, copied verbatim:

$\mu_l = \mathbb{E}(\text{# vertices on } l\text{-tree components}); \sum_{2}^k \mu_l = 2 \sum {n\choose l} l^{l-2} ( \frac{\gamma \log{n}}{n})^{l-1} (1 - \frac{\gamma \log{n}}{n})^{ln}$.

I'm unclear precisely what $\mu_l$ is actually meant to be defining the expectation of (the total number of vertices which lie in precisely one tree, of size exactly $l$, perhaps?), but am trying to deduce it from the sum.

So, as far as I can figure things, we're saying $\mu_l = 2 {n \choose{l}} l^{l-2}p^{l-1} (1-p)^{ln}$: it looks to me like $n \choose l$ arises as the number of ways you can choose $l$ of the $n$ vertices of the graph, $l^{l-2}$ is the total number of possible trees on these $l$ vertices (Cayley's formula) and $p^{l-1}$ is the probability of having the $(l-1)$ edges of the tree on $l$ vertices, as occurring in the expectation - whatever it is actually an expectation of.

However, I can't see where the factor of $2$ and the $(1-p)^{ln}$ come from: $(1-p)^j$ usually corresponds to fixing a certain number $j$ of edges as being not present in the graph, but for $j=nl$ that would suggest you want to have all possible edges from some $l$ vertices to some $n$ vertices not present; but $n$ vertices would of course be the entire graph, so that makes no sense. I wonder if it might be missing something, and should instead be (e.g.) $j=l(n-l)$?

Are the notes copied down wrong (I don't think they are, my friend's notes are identical), or is it just a matter of understanding what this expectation is being taken of? Or perhaps my equals sign should be an 'approximately equals'. I'm sure it'll be obvious as soon as someone points out what I'm missing, so don't worry about going into excessive detail with any answers, just a brief explanation of what the term might mean would be warmly welcomed, if you have any better ideas than me. Many thanks.

share|cite|improve this question
up vote 1 down vote accepted

I think this may be an "equals" vs. "approximately equals" issue.

Typically the tree components (or any component except for the giant component) will be of size much much smaller than $n$ (probably fixed in this case -- certainly at most $\log n$). Replacing $(1-p)^{\ell (n-\ell)}$ by $(1-p)^{\ell n}$ multiplies the expectation by $(1-p)^{\ell^2} \geq 1-p \ell^2 = 1-o(1)$.

Even if we didn't make the replacement, we'd still only have an approximation, since we're overcounting in the case where there's a small component with more than $\ell-1$ edges. So we might as well make things simpler.

The two still confuses me though. Assuming that $\mu_\ell$ is supposed to be counting the number of vertices in components of size exactly $\ell$, then you should be multiplying the number of components of size $\ell$ not by $2$, but by $\ell$. Is your proof by chance trying to get a lower bound on the expectation instead of the expectation itself?

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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