Branching process interpretation of giant component

353 Views Asked by At

I'm trying to understand the following intuitive interpretation of the relationship between branching processes and connected components in random graphs:

Blockquote

What is a bit confusing to me is how to imagine the survival of a vertex in a random graph. If a branching process "survives", then it goes on forever. Obviously, this can't happen in a finite graph. Surely the subtelty here is that we let $n \to \infty$. Is this the sense in which we can image the size of the giant component to be infinite? Is this why we can think of $n\zeta_{\lambda}$ as the expected size of the component of a randomly chosen vertex?

My other question is: why does this theorem allow us to conclude that there is a unique giant component in this setting?

1

There are 1 best solutions below

1
On BEST ANSWER

I strongly recommend reading the Random Graphs chapter of Alon and Spencer's Probabilistic Method to get this. Many of the ideas below come from there, and many great ideas not found below are there as well (including an intuitive explanation of why we choose the fine parametrization to be what it is).

The overall idea is that the graph branching process is well-approximated by the Poisson branching process for as long as it has a small number of descendants. To explain the deviation between them, suppose that the graph branching process has reached $\frac{n}{1000}$ vertices. Then each new branching step looks for edges to the remaining $\frac{999n}{1000}$ vertices, each edge being present with probability $\frac{\lambda}{n}$, and finds $\operatorname{Poisson}(\frac{999}{1000}\lambda)$ many descendants, rather than the $\operatorname{Poisson}(\lambda)$ it used to have earlier. Eventually, the expected value will fall below $1$, and the graph branching process will halt. (Alon and Spencer call this the ecological limitation.)

If the Poisson branching process dies out, its probability of having more than $D$ descendants drops exponentially in $D$, and therefore the largest components that correspond to an extinct branching process have size $O(\log n)$. If the Poisson branching process survives to infinity, the graph branching process startes deviating from it once it sees a linear number of vertices, and so the vertex ends up in a giant component.

If $\zeta_\lambda$ is the probability of the latter happening when we explore from a given vertex, then a priori the value $\zeta_\lambda n$ is just the expected number of vertices in linear-size components. With a more careful analysis, we can put a lower bound of $\delta n$ on the size of any linear-size component, but it would be very hard to make $\delta = \zeta_\lambda$.

(A rough idea of how we might get some $\delta$ is to say that for as long as we have seen fewer than $\frac{\lambda-1}{2\lambda}n$ vertices, our graph branching process is lower-bounded by a Poisson branching process with mean $(n - \frac{\lambda-1}{2\lambda}n)\cdot \frac{\lambda}{n} = \frac{\lambda+1}{2}$, which still exceeds $1$.)

But there's a way to go from "$\zeta_\lambda n$ vertices are in components of size at least $\delta n$" to "$\zeta_\lambda n$ of the vertices are in a single component". Alon and Spencer call it "sprinkling". The idea is to choose some probabily $p_1$, with $n^{-2} \ll p_1 \ll n^{-1}$, and a second probability $p_2 \sim \frac{\lambda}{n}$ satisfying $1 - \frac{\lambda}{n} = (1 -p_1)(1-p_2)$. Then the union of $\mathcal G_{n,p_1}$ and $\mathcal G_{n,p_2}$ has a $\mathcal G_{n,\lambda/n}$ distribution. We can do the above analysis for $\mathcal G_{n,p_2}$ (which is basically $\mathcal G_{n,\lambda/n}$) and then, once we get to this step, add the edges from $\mathcal G_{n,p_1}$ in. The edge probability $p_1$ is just high enough that two connected components of size $\delta n$ will receive an edge between them w.h.p., so in $\mathcal G_{n,\lambda/n}$, all linear-size components will end up as one connected component.

We still know that $\zeta_\lambda n$ is the expected number of vertices in a linear-size component, and now we know that there is only one linear-size component, and therefore that component has expected size $\zeta_\lambda n$.