Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí Department of Mathematic dành cho các bạn yêu thích môn toán học đề tài: Largest minimal percolating sets in hypercubes under 2-bootstrap percolation. | Largest minimal percolating sets in hypercubes under 2-bootstrap percolation Eric Riedl University of Notre Dame Department of Mathematics ebriedl@ Submitted Oct 10 2009 Accepted May 18 2010 Published May 25 2010 Mathematics Subject Classification 05D99 Abstract Consider the following process known as r-bootstrap percolation on a graph G. Designate some initial infected set A and infect any vertex with at least r infected neighbors continuing until no new vertices can be infected. We say A percolates if it eventually infects the entire graph. We say A is a minimal percolating set if A percolates but no proper subset percolates. We compute the size of a largest minimal percolating set for r 2 in the n-dimensional hypercube. 1 Introduction In this paper we consider the following process known as r-bootstrap percolation. Designate an initial set A of infected vertices. Let Ao A. Then let At be the set of vertices in At-1 union the set of vertices which have at least r neighbors in At-1. Set A UịAị and call A the set of vertices infected by A. A set A percolates if it infects the entire graph. A percolating set A is said to be minimal if for all v G A the set A v does not percolate. Let E G r be the largest size of a minimal percolating set and let m G r be the smallest size of a necessarily minimal percolating set. In this paper we find E Qn 2 where Qn is the n-dimensional hypercube and we use similar techniques to find bounds on E n d 2 for all n and d. Since r 2 for most of this paper we write E G for E G 2 without ambiguity. Bootstrap percolation was introduced in 1979 by Chalupa Leath and Reich 9 for its applications to dilute magnetic sytems. For more information on the many physical applications of bootstrap percolation see the survey article by Adler and Lev 1 . Arising naturally from the physical context is the following probabilistic problem. Let each vertex of G be initially infected independently with probability p. Then what is the probability .
