BOOTSTRAP PERCOLATION IN THREE DIMENSIONS

• 成果类型: Article
• 署名作者: Balogh, Jozsef; Bollobas, Bela; Morris, Robert
• 署名单位: University of Illinois System; University of Illinois Urbana-Champaign; University of Cambridge; University of Memphis; University of Cambridge
• 刊物名称: ANNALS OF PROBABILITY
• ISSN/ISSBN: 0091-1798
• DOI: 10.1214/08-AOP433
• 发表日期: 2009
• 页码: 1329-1380
• 关键词: metastability threshold; inequalities; hypercube; BEHAVIOR; models; PROOF; graph

摘要

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 r is an element of N previously infected neighbors. When the set A is chosen at randorn, 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) = Theta (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)) pi(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.