Bootstrap percolation on Galton-Watson trees

Consider a rooted Galton-Watson tree $T$, to each of whose edges we assign, independently, a weight that equals $+1$ with probability $p_{1}$, $0$ with probability $p_{0}$ and $-1$ with probability $p_{-1}=1-p_{1}-p_{0}$. We play a game on this rooted, edge-weighted Galton-Watson tree, involving two players and a token. The token is allowed to be moved from where it is currently located, say a vertex $u$ of $T$, to any child $v$ of $u$. The players begin with initial capitals...

We consider invasion percolation on Galton-Watson trees. On almost every Galton-Watson tree, the invasion cluster almost surely contains only one infinite path. This means that for almost every Galton-Watson tree, invasion percolation induces a probability measure on infinite paths from the root. We show that under certain conditions of the progeny distribution, this measure is absolutely continuous with respect to the limit uniform measure. This confirms that invasion percol...

Let $\mathcal{T}$ be a supercritical Galton-Watson tree with a bounded offspring distribution that has mean $\mu >1$, conditioned to survive. Let $\varphi_{\mathcal{T}}$ be a random embedding of $\mathcal{T}$ into $\mathbb{Z}^d$ according to a simple random walk step distribution. Let $\mathcal{T}_p$ be percolation on $\mathcal{T}$ with parameter $p$, and let $p_c = \mu^{-1}$ be the critical percolation parameter. We consider a random walk $(X_n)_{n \ge 1}$ on $\mathcal{T}_p$...

Consider independent bond percolation with retention probability p on a spherically symmetric tree Gamma. Write theta_Gamma(p) for the probability that the root is in an infinite open cluster, and define the critical value p_c=inf{p:theta_Gamma(p)>0}. If theta_Gamma(p_c)=0, then the root may still percolate in the corresponding dynamical percolation process at the critical value p_c, as demonstrated recently by Haggstrom, Peres and Steif. Here we relate this phenomenon to the...

In majority bootstrap percolation on a graph G, an infection spreads according to the following deterministic rule: if at least half of the neighbours of a vertex v are already infected, then v is also infected, and infected vertices remain infected forever. Percolation occurs if eventually every vertex is infected. The elements of the set of initially infected vertices, A \subset V(G), are normally chosen independently at random, each with probability p, say. This process ...

We give a characterization of the percolation threshold for a multirange model on oriented trees, as the first positive root of a polynomial, with the use of a multi-type Galton-Watson process. This gives in particular the exact value of the critical point for the model studied in [2] and [3] for k = 2.

We are interested in the randomly biased random walk on the supercritical Galton--Watson tree. Our attention is focused on a slow regime when the biased random walk $(X_n)$ is null recurrent, making a maximal displacement of order of magnitude $(\log n)^3$ in the first $n$ steps. We study the localization problem of $X_n$ and prove that the quenched law of $X_n$ can be approximated by a certain invariant probability depending on $n$ and the random environment. As a consequenc...

We study oriented percolation on random causal triangulations, those are random planar graphs obtained roughly speaking by adding horizontal connections between vertices of an infinite tree. When the underlying tree is a geometric Galton--Watson tree with mean $m>1$, we prove that the oriented percolation undergoes a phase transition at $p_c(m)$, where $p_c(m) = \frac{\eta}{1+\eta}$ with $\eta = \frac{1}{m+1} \sum_{n \geq 0} \frac{m-1}{m^{n+1}-1}$. We establish that strictly ...

We provide sufficient conditions for a regular graph $G$ of growing degree $d$, guaranteeing a phase transition in its random subgraph $G_p$ similar to that of $G(n,p)$ when $p\cdot d\approx 1$. These conditions capture several well-studied graphs, such as (percolation on) the complete graph $K_n$, the binary hypercube $Q^d$, $d$-regular expanders, and random $d$-regular graphs. In particular, this serves as a unified proof for these (and other) cases. Suppose that $G$ is a...

When considering statistical mechanics models on trees, such that the Ising model, percolation, or more generally the random cluster model, some concave tree recursions naturally emerge. Some of these recursions can be compared with non-linear conductances, or $p$-conductances, between the root and the leaves of the tree. In this article, we estimate the $p$-conductances of $T_n$, a supercritical Galton-Watson tree of depth $n$, for any $p>1$ (for a quenched realization of $T...