Majority Bootstrap Percolation on the Hypercube：大多数引导渗透在超立方体.pdf

MAJORITY BOOTSTRAP PERCOLATION ON THE HYPERCUBE J ′OZSEF BALOGH, B ′ELA BOLLOB ′AS, AND ROBERT MORRIS majority bootstrap percolation on a graphG, an infection spreads according to the following deterministic rule: if at least half of the neighbours of a vertexvare already infected, then vis also infected, and infected vertices remain infected forever. Percolation occurs if eventually every vertex is infected. The elements of the set of initially infected vertices,A?V(G), are normally chosen independently at random, each with proba- bilityp, say. This process has been extensively studied on the sequence of torus graphs [n] d, forn= 1,2, . . ., whered=d(n) is either ?xed or a very slowly growing function ofn. For example, Cerf and Manzo [14] showed that the critical probability iso(1) if d(n)6log ?n, ., ifp=p(n) is bounded away from zero then the probability of percolation on [n] dtends to one asn→∞. In this paper we study the case when the growth ofdto∞is not excessively slow; in particular, we show that the critical probability is 1/2+o(1) ifd>(log logn) 2log log logn, and give much stronger bounds in the case thatGis the hypercube, [2] d. Consider a ?nite graphGwith two parameters,q vandr v, attached to each vertexv, withq v+r vgreater than the degree ofv. Suppose each of the vertices may take either one of two states, ‘active’ and ‘inactive’, say. At each instant, some of the vertices may ‘wake up’ at random; whenever a vertexvdoes so, if at leastq vof its neighbours are active then it es active, if at leastr vof its neighbours are inactive then it es inactive, and if neither of these cases holds thenvkeeps its state. Given an initial distribution of active sites, one can then ask what happens to the system in the long run. For example, we may takeGto be ad-regular graph withdodd, and parametersq v=r v= (d+ 1)/2 for every vertexv: in this case, The ?rst author was supported during this research by OTKAgrant T049398 and NSF