Bootstrap Percolation on the Hamming Torus
Bootstrap Percolation on the Hamming Torus
复制标题
汉明环上的 Bootstrap 渗透
DOI：
--
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
David J Sivakoff
中科院分区：
文献类型：
--
作者：
Janko Gravner;C. Hoffman;James Pfeiffer;David J Sivakoff
尺寸$ d $的锤子圆环是带有顶点$ \ {1，\ dots，n \}^d $的图形，并且在单个坐标中有不同的两个顶点之间的边缘。带有阈值$ \ theta $的bootstrap Percolation从一个随机的开放顶点开始，每个顶点都独立于概率$ p $，并且在每个时间步骤中，开放式设置都会通过与每个顶点相邻至少$ \ theta $ open来生长邻居。我们假设$ n $很大，对于某些$ \ alpha> 1 $，$ p $ scales as $ n^{ - \ alpha} $，并研究了$ i $ dimensional subgraph曾经打开的概率。对于大$ \ theta $，我们证明关键指数$ \ alpha $的$ 1+d/\ theta $ for $ i = 1 $，约为$ 1+2/\ theta+\ \ \ \ theta（\ theta^{ - 3 /2}）$ for $ i \ ge2 $。我们的小$ \ theta $结果大多限于$ d = 3 $，在许多情况下，我们确定了关键的$ \ alpha $，当$ \ theta = 3 $时，准确地计算了整个图最终的关键概率打开。
The Hamming torus of dimension $d$ is the graph with vertices $\{1,\dots,n\}^d$ and an edge between any two vertices that differ in a single coordinate. Bootstrap percolation with threshold $\theta$ starts with a random set of open vertices, to which every vertex belongs independently with probability $p$, and at each time step the open set grows by adjoining every vertex with at least $\theta$ open neighbors. We assume that $n$ is large and that $p$ scales as $n^{-\alpha}$ for some $\alpha>1$, and study the probability that an $i$-dimensional subgraph ever becomes open. For large $\theta$, we prove that the critical exponent $\alpha$ is about $1+d/\theta$ for $i=1$, and about $1+2/\theta+\Theta(\theta^{-3/2})$ for $i\ge2$. Our small $\theta$ results are mostly limited to $d=3$, where we identify the critical $\alpha$ in many cases and, when $\theta=3$, compute exactly the critical probability that the entire graph is eventually open.