1
$\begingroup$

Question in exam paper. Given an undirected G(n, p) graph with p=1.2/n , what is the expected size of its giant component?

Note: I know that there is a giant component because np = 1.2 > 1 and that the other small components are of size O(log n). I think however that this questions wants a real number like 1.2n or something. What is that number and how do you find it?

$\endgroup$
  • 1
    $\begingroup$ In the limit $n\to\infty$, the size of the giant component behaves like $sn$ where $s>0$ solves $$1-s=e^{-1.2s}$$ $\endgroup$ – Did Apr 12 '18 at 14:05
1
$\begingroup$

The basic idea is that the probability that a given vertex ends up in the giant component is equal to the probability that its associated branching process (with mean $np = 1.2$) becomes infinite.

If $q$ is the probability that the branching process goes extinct, then by conditioning on the number of children of the first node, we have $$ q = \sum_{i \ge 0} q^i \cdot \left(e^{-1.2} \frac{1.2^i}{i!}\right) $$ which simplifies to $q = e^{-1.2(1-q)}$. Therefore if $r$ is the probability of being in the giant component, then it is the nonzero solution to $1-r = e^{-1.2r}$, and $nr$ vertices of the graph end up in the giant component.

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