I was just looking a book and the book said For a graph in supercritical regime (np > 1). For the small component (size s) not a part of giant component, it is a tree (which means the number of edges in the small component is s - 1). So, anyone who can tell me how to prove it?


  • $\begingroup$ The "supercritical regime" is not the same as $np > 1$. For example, if $p = \frac1n + \frac1{n^2}$, we are still within the critical window and there is no giant component. $\endgroup$ – Misha Lavrov Mar 10 at 0:48

This is false. You can say that the small components are simple meaning that they contain at most one cycle, but you cannot guarantee that they are all trees.

For instance, let's consider $p = \frac cn$ (for any positive real $c$, whether it is bigger than $1$ or not) and count the components which are triangles. Let $X$ be the number of such components.

The probability that three given vertices induce a triangle component is $p^3 (1-p)^{3(n-3)} \sim p^3 e^{-3np} = p^3 e^{-3c}$ and since there are $\binom n3 \sim \frac{n^3}{6}$ ways to choose three vertices, we have (multiplying these together) $\mathbb E[X] \sim \frac{c^3}{6} e^{-3c}$.

To compute $\mathbb E[X^2]$, we count the number of ordered pairs of triangle components. There are $X$ pairs in which a component is paired with itself. As for pairs of two distinct components, there are $\binom n3 \binom{n-3}3 \sim \frac{n^6}{36}$ ways to choose their vertices, and the probability is $p^6 (1-p)^{6(n-6)+9} \sim p^6 e^{-6c}$ that any given choice induces two triangle components, so in expectation (by multiplying these together) there are $\frac{c^6}{36} e^{-6c}$ such pairs. Therefore $\mathbb E[X^2] \sim \frac{c^3}{6}e^{-3c} + \frac{c^6}{36} e^{-6c}$, and $\mathrm{Var}[X] \sim \frac{c^3}{6}e^{-3c}$.

Now apply the one-sided Chebyshev's inequality to conclude that $$ \Pr[X = 0] \le \frac{\mathrm{Var}[X]}{\mathbb E[X^2]} \sim \frac{\frac{c^3}{6}e^{-3c}}{\frac{c^3}{6}e^{-3c} + \frac{c^6}{36} e^{-6c}} = \frac{1}{1 + \frac{c^3}{6}e^{-3c}}. $$ For any constant $c>0$, this is bounded away from $1$ as $n \to \infty$, and so there is a constant positive probability of finding triangle components.

(These are only one example of non-tree small components; they are just the easiest to analyze.)


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.