Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Background and definitions

Consider a random graph on $n$ vertices with a nicely behaved degree sequence. That is, letting $d_i(n)$ denote the number of vertices of degree $i$, suppose that for all $i$, there exists a constant $\lambda_i$ such that $d_i(n)/n \to \lambda_i$ as $n \to \infty$.

Let $G$ be a randomly chosen graph with this degree sequence. Molloy and Reed proved that as $n \to \infty$, if $\sum_{i = 0}^{\infty} i(i - 2)\lambda_i > 0$, then w.h.p. $G$ has a giant component, while if $\sum_{i = 0}^{\infty} i(i - 2)\lambda_i < 0$, then w.h.p. $G$ does not have a giant component.

Moreover, the same authors gave a formula for the limiting size of the giant component in the former case.

My question concerns the "small" components in the case where a giant component exists. In the case of an Erdos-Renyi random graph $G_{n,p}$, the structure of these components is well understood: if $p = cn/2$ for some $c > 1$, then with high probability the graph is the union of the giant component, small tree components, and a growing but relatively small number of unicyclic components. (For a precise statement of this, see Theorem 6.11 of Bollobas's Random Graphs.)

My question

For which degree sequences is it true that with high probability the small components are mostly trees with a comparatively small number of unicyclic components? In some cases, it's easy to see that no small component can be a tree: for example, in the case of an $r$-regular graph for $r \geq 2$, $G$ cannot contain a tree, because every tree has a vertex of degree $1$. (However, for $r \geq 3$, the results in the second paper linked to above show that w.h.p. the giant component consists of the entire graph, so in this case the desired property holds vacuously.) So, for which degree sequences is it "non-trivially" true that most small components are trees?

(N.B.: In the first paper linked to above, Molloy and Reed showed that in the "subcritical" case in which there is no giant component, w.h.p. every component contains at most one cycle.)

The motivation

I'm teaching a course on complex networks using M.E.J. Newman's Networks: An Introduction. In the chapter on random graphs with a given degree sequence (see SEction 13.7), the author claims that for essentially any given degree sequence, almost all of the small components are trees. However, the argument given is far from rigorous, and I am rather skeptical of the conclusion.

share|improve this question

1 Answer 1

up vote 2 down vote accepted

I think the answer to your question is: It is "non-trivially" true that most small components are trees for all degree sequences where the giant component is not the whole graph.

The answer comes from the two papers you provided. Theorem 2 of the second paper gives what they call a "Discrete Duality Principle" which basically says that if you remove the giant component, then the remaining graph looks like a random graph on the remaining vertices with degree sequence given by these $\lambda_i'$s (which they provide to you).

The $\lambda_i'$s will satisfy the $Q(\mathcal{D}) < 0$ condition, so you can apply Theorem 1(b) from the first paper to conclude that the random graph with that degree sequence is mostly tree components (as you pointed out).

I hope this is right, I don't know anything about this other than the two papers you provided.

share|improve this answer

Your Answer

 
discard

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.