Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: Minimal percolating sets in bootstrap percolation. | Minimal percolating sets in bootstrap percolation Robert Morris Murray Edwards College The University of Cambridge Cambridge CB3 0DF England rdm30@ Submitted May 26 2008 Accepted Dec 7 2008 Published Jan 7 2009 Mathematics Subject Classification 05D99 Abstract In standard bootstrap percolation a subset A of the grid n 2 is initially infected. A new site is then infected if at least two of its neighbours are infected and an infected site stays infected forever. The set A is said to percolate if eventually the entire grid is infected. A percolating set is said to be minimal if none of its subsets percolate. Answering a question of Bollobás we show that there exists a minimal percolating set of size 4n2 33 o n2 but there does not exist one larger than n 2 2 6. 1 Introduction Consider the following deterministic process on a finite connected graph G. Given an initial set of infected sites A c V G a vertex becomes infected if at least r 2 N of its neighbours are already infected and infected sites remain infected forever. This process is known as r-neighbour bootstrap percolation on G. If eventually the entire vertex set becomes infected we say that the set A percolates on G. For a given graph G we would like to know which sets percolate. The bootstrap process was introduced in 1979 by Chalupa Leith and Reich 14 . It is an example of a cellular automaton and is related to interacting systems of particles for example it has been used as a tool in the study of the Ising model at zero-temperature see 15 and 18 . For more on the various physical motivations and applications of bootstrap percolation we refer the reader to the survey article of Adler and Lev 1 and the references therein. Bootstrap percolation has been extensively studied in the case where G is the d-dimensional grid n d 1 n d with edges induced by the lattice Zd and the elements of the set A are chosen independently at random with probability p p n . In The author was supported during this research .
