Bootstrap percolation is a type of cellular automaton which has been used to model various physical phenomena, such as ferromagnetism. For each natural number $r$, the $r$-neighbour bootstrap process is an update rule for vertices of a graph in one of two states: `infected' or `healthy'. In consecutive rounds, each healthy vertex with at least $r$ infected neighbours becomes itself infected. Percolation is said to occur if every vertex is eventually infected.?Usually, the starting set of infected vertices is chosen at random, with all vertices initially infected independently with probability $p$. In that case, given a graph $G$ and infection threshold $r$, a quantity of interest is the critical probability, $p_c(G,r)$, at which percolation becomes likely to occur. In this paper, we look at infinite trees and, answering a problem posed by Balogh, Peres and Pete, we show that for any $b geq r$ and for any $epsilon > 0$ there exists a tree $T$ with branching number $operatorname{br}(T) = b$ and critical probability $p_c(T,r) 0$ such that if $T$ is a Galton- Watson tree with branching number $operatorname{br}(T) = b geq r$ then $$p_c(T,r) > rac{c_r}{b} e^{-rac{b}{r-1}}.$$ We also show that this bound is sharp up to a factor of $O(b)$ by giving an explicit family of Galton--Watson trees with critical probability bounded from above by $C_r e^{-rac{b}{r-1}}$ for some constant $C_r>0$.
展开▼
机译：引导渗滤是一种细胞自动机，已被用来模拟各种物理现象，例如铁磁性。对于每个自然数$ r $，$ r $邻居引导程序是针对以下两种状态之一的图形顶点的更新规则：“感染”或“健康”。在连续的回合中，每个被邻居感染至少r $$的健康顶点都会自身感染。如果每个顶点最终都被感染，则会发生渗滤。通常，随机选择感染顶点的起始集合，所有顶点最初都是独立感染的，概率为$ p $。在那种情况下，给定图表$ G $和感染阈值$ r $，感兴趣的数量是临界概率$ p_c（G，r）$，在该概率处可能发生渗滤。在本文中，我们研究了无限树，并回答了Balogh，Peres和Pete提出的问题，我们表明对于任何$ b geq r $和任何$ epsilon> 0 $，都存在一个带有$ T $的树分支编号$ operatorname {br}（T）= b $和临界概率$ p_c（T，r）0 $使得如果$ T $是分支编号为$ operatorname {br}（T）的高尔顿-沃森树= b geq r $，然后$$$ p_c（T，r）> frac {c_r} {b} e ^ {- frac {b} {r-1}}。$$我们还证明了这个界限很尖锐通过给出一个显式的高尔顿-沃森树族，其临界概率从上面以$ C_r e ^ {- frac {b} {r-1}} $$为边界，给出高达$ O（b）$的因数$ C_r> 0 $。
展开▼
