How to find percolation threshold for trees?

232 Views Asked by At

Let $\mathbb{T}_k$ denote the rooted tree where each node has $k$ children.

How do I show that the percolation threshold for the ternary tree, $p_c(\mathbb{T}_3)=\frac{1}{3}$, and how do I find the general formula for $p_c(\mathbb{T}_k)$ for $k\geq 4$?

1

There are 1 best solutions below

0
On

It seems you are referring to the $k$-ary tree, where every node has $k$ children, rather than the $k$-regular tree, where every node has degree $k$.

If $p<1/k$ then the number $N_m$ of level $m$ vertices that are connected to the root satisfies $E_p(N_m)=(kp)^m \to 0$, so with probability 1, the cluster of the root is finite. The same applies to any other node, so there is no infinite cluster almost surely.

If $p>1/k$, then $E_p(N_m) =(kp)^m \to \infty$, and
$$ E_p (N_m^2) \le \sum_{j=0}^m (kp)^j (kp)^{2m-2j}=O\bigl((kp)^{2m}\bigr) \,.$$ By the 2nd moment method, e.g., the Paley-Zygmund inequality [1], $$P_p\bigl(N_m>(kp)^m/2\bigr) \ge \frac{E_p(N_m)^2}{4E_p(N_m^2)} \,,$$ this implies that with positive probability, the cluster of the root is infinite. By the Kolmogorov zero-one law, with probability 1 there is an infinite cluster.

Read about Galton-Watson branching processes to see another approach. Several chapters of the book [2] concern extensions of this fact.

[1] https://en.wikipedia.org/wiki/Paley%E2%80%93Zygmund_inequality

[2] https://www.yuval-peres-books.com/probability-on-trees-and-networks/