BOOTSTRAP PERCOLATION ON THE HAMMING TORUS

• 成果类型: Article
• 署名作者: Gravner, Janko; Hoffman, Christopher; Pfeiffer, James; Sivakoff, David
• 署名单位: University of California System; University of California Davis; University of Washington; University of Washington Seattle; Duke University
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• DOI: 10.1214/13-AAP996
• 发表日期: 2015
• 页码: 287-323
• 关键词: cellular-automata; random subgraphs; sharp threshold; graph; dimensions; hypercube

摘要

The Hamming torus of dimension d is the graph with vertices {1,...,n}(d) and an edge between any two vertices that differ in a single coordinate. Bootstrap percolation with threshold 9 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 9 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 0, we prove that the critical exponent a is about 1 -I- dI0 for i = 1, and about 1 210 + 8(9-312) for i > 2. Our small 0 results are mostly limited to d =3, where we identify the critical a in many cases and, when 9 =3, compute exactly the critical probability that the entire graph is eventually open.