Bootstrap percolation in three dimensions
Bootstrap percolation in three dimensions
复制标题
三个维度的 Bootstrap 渗透
DOI：
--
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
R. Morris
中科院分区：
文献类型：
--
作者：
J. Balogh;B. Bollob'as;R. Morris
所谓自助渗流，我们指的是图G上的以下确定性过程。给定一组在时间0“感染”的顶点A，如果新的顶点至少有∈ N个先前感染的邻居，则它们随后在每个时间步被感染。当随机选择集合A时，主要目的是确定临界概率pc（G，r），在该概率下，渗流（感染整个图）变得可能发生。这个自举过程在d维网格[n] d上得到了广泛的研究：当2 ≤ r ≤ d固定时，Cerf和Cirillo（d = r = 3）以及Cerf和Manzo（一般情况下）证明了pc（[n] d，r）=Θ（1/log（r-1）n）d-r+1，其中log（r）是r次重对数。然而，精确的阈值函数只在d = r = 2的情况下才知道，其中Holroyd表明它是（1 + o（1））π 2 18 log n。在本文中，我们将确定在d = r = 3的关键情况下的精确阈值，并为解决所有固定d和r的问题奠定基础。
By bootstrap percolation we mean the following deterministic process on a graph G. Given a set A of vertices "infected" at time 0, new vertices are subsequently infected, at each time step, if they have at least ∈ N previously infected neighbors. When the set A is chosen at random, the main aim is to determine the critical probability p c (G, r) at which percolation (infection of the entire graph) becomes likely to occur. This bootstrap process has been extensively studied on the d-dimensional grid [n] d : with 2 ≤ r ≤ d fixed, it was proved by Cerf and Cirillo (for d = r = 3), and by Cerf and Manzo (in general), that p c ([n] d ,r)=Θ(1/log (r-1) n) d-r+1 , where log (r) is an r-times iterated logarithm. However, the exact threshold function is only known in the case d = r = 2, where it was shown by Holroyd to be (1 + o(1)) π 2 18 log n. In this paper we shall determine the exact threshold in the crucial case d = r = 3, and lay the groundwork for solving the problem for all fixed d and r.