Hostname: page-component-848d4c4894-x5gtn Total loading time: 0 Render date: 2024-06-04T12:55:30.685Z Has data issue: false hasContentIssue false
  • English
  • Français

Majority Bootstrap Percolation on the Hypercube

Published online by Cambridge University Press:  01 March 2009

JÓZSEF BALOGH ,
BÉLA BOLLOBÁS  and
ROBERT MORRIS
JÓZSEF BALOGH
Affiliation:
Department of Mathematics, University of Illinois, 1409 W. Green Street, Urbana, IL 61801, USA (e-mail: jobal@math.uiuc.edu)
BÉLA BOLLOBÁS
Affiliation:
Trinity College, Cambridge CB2 1TQ, UK and Department of Mathematical Sciences, University of Memphis, Memphis, TN 38152, USA (e-mail: B.Bollobas@dpmms.cam.ac.uk)
ROBERT MORRIS
Affiliation:
Murray Edwards College, University of Cambridge, Cambridge CB3 0DF, UK (e-mail: rdm30@cam.ac.uk)
Get access Rights & Permissions [Opens in a new window]

Abstract

In majority bootstrap percolation on a graph G, an infection spreads according to the following deterministic rule: if at least half of the neighbours of a vertex v are already infected, then v is also infected, and infected vertices remain infected forever. We say that 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 probability p, say. This process has been extensively studied on the sequence of torus graphs [n]d, for n = 1,2, . . ., where d = d(n) is either fixed or a very slowly growing function of n. For example, Cerf and Manzo [17] showed that the critical probability is o(1) if d(n) ≤ log*n, i.e., if p = p(n) is bounded away from zero then the probability of percolation on [n]d tends to one as n → ∞.

In this paper we study the case when the growth of d to ∞ is not excessively slow; in particular, we show that the critical probability is 1/2 + o(1) if d ≥ (log log n)2 log log log n, and give much stronger bounds in the case that G is the hypercube, [2]d.

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 18 , Issue 1-2: Papers from The 2006 Oberwolfach Meeting on Combinatorics, Probability and Computing , March 2009 , pp. 17 - 51
Copyright
Copyright © Cambridge University Press 2008

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1]Adler, J. and Lev, U. (2003) Bootstrap percolation: Visualizations and applications. Braz. J. Phys. 33 641–644.CrossRefGoogle Scholar
[2]Aizenman, M.. and Lebowitz, J. L. (1988) Metastability effects in bootstrap percolation. J. Phys. A 21 3801–3813.CrossRefGoogle Scholar
[3]Ajtai, M., Komlós, J. and Szemerédi, E. (1982) Largest random component of a k-cube. Combinatorica 2 1–7.CrossRefGoogle Scholar
[4]Balister, P., Bollobás, B., Johnson, R. and Walters, M. (2003) Random majority percolation. Random Struct. Alg., Submitted.Google Scholar
[5]Balogh, J. and Bollobás, B. (2006) Bootstrap percolation on the hypercube. Probab. Theory Rel. Fields 134 624–648.CrossRefGoogle Scholar
[6]Balogh, J., Bollobás, B. and Morris, R. Majority bootstrap percolation on the hypercube. arXiv.org/abs/math/0702373.Google Scholar
[7]Balogh, J., Bollobás, B. and Morris, R. Bootstrap percolation in three dimensions. Submitted.Google Scholar
[8]Balogh, J., Bollobás, B. and Morris, R. The sharp threshold for r-neighbour bootstrap percolation. In preparation.Google Scholar
[9]Balogh, J., Bollobás, B. and Morris, R. Bootstrap percolation on [n]d. In preparation.Google Scholar
[10]Balogh, J., Peres, Y. and Pete, G. (2006) Bootstrap percolation on infinite trees and non-amenable groups. Combin. Probab. Comput. 15 715–730.CrossRefGoogle Scholar
[11]Balogh, J. and Pittel, B. (2007) Bootstrap percolation on random regular graphs. Random Struct. Alg. 30 257–286.CrossRefGoogle Scholar
[12]Baranyai, Z. (1975) On the factorization of the complete uniform hypergraph. In Infinite and Finite Sets (Colloq. Keszthely, 1973; dedicated to P. Erd Hos on his 60th birthday), Vol. I, pp. 91–108.Google Scholar
[13]Bollobás, B. (2001) Random Graphs, 2nd edn, Cambridge University Press.CrossRefGoogle Scholar
[14]Bollobás, B., Kohayakawa, Y. and Luczak, T. (1992) The evolution of random subgraphs of the cube. Random Struct. Alg. 3 55–90.CrossRefGoogle Scholar
[15]Borgs, C., Chayes, J. T., vander Hofstad, R. der Hofstad, R., Slade, G. and Spencer, J. (2006) Random subgraphs of finite graphs III: The phase transition for the n-cube. Combinatorica 26 395–410.CrossRefGoogle Scholar
[16]Cerf, R. and Cirillo, E. N. M. (1999) Finite size scaling in three-dimensional bootstrap percolation. Ann. Probab. 27 1837–1850.CrossRefGoogle Scholar
[17]Cerf, R. and Manzo, F. (2002) The threshold regime of finite volume bootstrap percolation. Stochastic Proc. Appl. 101 69–82.CrossRefGoogle Scholar
[18]Chalupa, J., Leath, P. L. and Reich, G. R. (1979) Bootstrap percolation on a Bethe lattice. J. Phys. C 12 L31–L35.CrossRefGoogle Scholar
[19]ErdHos, P. Hos, P. and Spencer, J. (1979) Evolution of the n-cube. Comput. Math. Appl. 5 33–39.Google Scholar
[20]Fontes, L. R., Schonmann, R. H. and Sidoravicius, V. (2002) Stretched exponential fixation in stochastic Ising models at zero temperature. Commun. Math. Phys. 228 495–518.CrossRefGoogle Scholar
[21]vander Hofstad, R. der Hofstad, R. and Slade, G. (2005) Asymptotic expansion in n −1 for percolation critical values on the n-cube and Z n. Random Struct. Alg. 27 331–357.Google Scholar
[22]vander Hofstad, R. der Hofstad, R. and Slade, G. (2006) Expansion in n −1 for percolation critical values on the n-cube and Z n: The first three terms. Combin. Probab. Comput. 15 695–713.Google Scholar
[23]Holroyd, A. (2003) Sharp metastability threshold for two-dimensional bootstrap percolation. Probab. Theory Rel. Fields 125 195–224.CrossRefGoogle Scholar
[24]Leighton, T. and Plaxton, C. G. (1998) Hypercubic sorting networks. SIAM J. Comput. 27 1–47.CrossRefGoogle Scholar
[25]McCulloch, W. S. and Pitts, W. (1943) A logical calculus of ideas immanent in nervous activity. Bull. Math. Biophys. 5 115–133.CrossRefGoogle Scholar
[26]Morris, R. Glauber dynamics in high dimensions. Submitted.Google Scholar
[27]Nanda, S., Newman, C. M. and Stein, D. (2000) Dynamics of Ising spin systems at zero temperature. In On Dobrushin's way (From Probability Theory to Statistical Mechanics (R. Minlos, S. Shlosman and Y. Suhov, eds). Amer. Math. Soc. Transl. (2) 198 183–194.Google Scholar
[28]Newman, C. M. and Stein, D. (2000) Zero-temperature dynamics of Ising spin systems following a deep quench: Results and open problems. Physica A 279 159–168.CrossRefGoogle Scholar
[29]Schonmann, R. H. (1990) Finite size scaling behavior of a biased majority rule cellular automaton. Physica A 167 619–627.CrossRefGoogle Scholar
[30]Schonmann, R. H. (1992) On the behaviour of some cellular automata related to bootstrap percolation. Ann. Probab. 20 174–193.CrossRefGoogle Scholar