Document Open Access Logo

Two Phase Transitions in Two-Way Bootstrap Percolation

Author Ahad N. Zehmakan

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2019.5.pdf
  • Filesize: 0.67 MB
  • 21 pages

Document Identifiers

Author Details

Ahad N. Zehmakan
  • ETH Zurich, Switzerland

Acknowledgements

The author likes to thank Raphael Cerf, Bernd Gärtner, and Roberto H. Schonmann for several stimulating discussions.

Cite AsGet BibTex

Ahad N. Zehmakan. Two Phase Transitions in Two-Way Bootstrap Percolation. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 5:1-5:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.ISAAC.2019.5

Abstract

Consider a graph G and an initial random configuration, where each node is black with probability p and white otherwise, independently. In discrete-time rounds, each node becomes black if it has at least r black neighbors and white otherwise. We prove that this basic process exhibits a threshold behavior with two phase transitions when the underlying graph is a d-dimensional torus and identify the threshold values.

Subject Classification

ACM Subject Classification
  • Theory of computation
Keywords
  • bootstrap percolation
  • cellular automata
  • phase transition
  • d-dimensional torus
  • r-threshold model
  • biased majority

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Joan Adler and Amnon Aharony. Diffusion percolation. I. Infinite time limit and bootstrap percolation. Journal of Physics A: Mathematical and General, 21(6):1387, 1988. Google Scholar
  2. Michael Aizenman and Joel L Lebowitz. Metastability effects in bootstrap percolation. Journal of Physics A: Mathematical and General, 21(19):3801, 1988. Google Scholar
  3. Paul Balister, Béla Bollobás, J Robert Johnson, and Mark Walters. Random majority percolation. Random Structures & Algorithms, 36(3):315-340, 2010. Google Scholar
  4. Paul Balister, Béla Bollobás, and Paul Smith. The time of bootstrap percolation in two dimensions. Probability Theory and Related Fields, 166(1-2):321-364, 2016. Google Scholar
  5. József Balogh and Béla Bollobás. Bootstrap percolation on the hypercube. Probability Theory and Related Fields, 134(4):624-648, 2006. Google Scholar
  6. József Balogh, Béla Bollobás, Hugo Duminil-Copin, and Robert Morris. The sharp threshold for bootstrap percolation in all dimensions. Transactions of the American Mathematical Society, 364(5):2667-2701, 2012. Google Scholar
  7. József Balogh, Béla Bollobás, and Robert Morris. Bootstrap percolation in three dimensions. The Annals of Probability, pages 1329-1380, 2009. Google Scholar
  8. József Balogh and Gábor Pete. Random disease on the square grid. Random Structures and Algorithms, 13(3-4):409-422, 1998. Google Scholar
  9. József Balogh and Boris G Pittel. Bootstrap percolation on the random regular graph. Random Structures & Algorithms, 30(1-2):257-286, 2007. Google Scholar
  10. George Barmpalias, Richard Elwes, and Andrew Lewis-Pye. Unperturbed Schelling segregation in two or three dimensions. Journal of Statistical Physics, 164(6):1460-1487, 2016. Google Scholar
  11. George Barmpalias, Richard Elwes, and Andy Lewis-Pye. Tipping points in 1-dimensional Schelling models with switching agents. Journal of Statistical Physics, 158(4):806-852, 2015. Google Scholar
  12. Christina Brandt, Nicole Immorlica, Gautam Kamath, and Robert Kleinberg. An analysis of one-dimensional Schelling segregation. In Proceedings of the forty-fourth annual ACM symposium on Theory of computing, pages 789-804. ACM, 2012. Google Scholar
  13. Raphaël Cerf and Emilio NM Cirillo. Finite size scaling in three-dimensional bootstrap percolation. Annals of probability, pages 1837-1850, 1999. Google Scholar
  14. Raphaël Cerf and Francesco Manzo. The threshold regime of finite volume bootstrap percolation. Stochastic Processes and their Applications, 101(1):69-82, 2002. Google Scholar
  15. Ching-Lueh Chang and Yuh-Dauh Lyuu. Bounding the sizes of dynamic monopolies and convergent sets for threshold-based cascades. Theoretical Computer Science, 468:37-49, 2013. Google Scholar
  16. Tom Coker and Karen Gunderson. A sharp threshold for a modified bootstrap percolation with recovery. Journal of Statistical Physics, 157(3):531-570, 2014. Google Scholar
  17. Devdatt P Dubhashi and Alessandro Panconesi. Concentration of measure for the analysis of randomized algorithms. Cambridge University Press, 2009. Google Scholar
  18. Richard Durrett, Jeffrey E Steif, et al. Fixation results for threshold voter systems. The Annals of Probability, 21(1):232-247, 1993. Google Scholar
  19. Paola Flocchini, Elena Lodi, Fabrizio Luccio, Linda Pagli, and Nicola ro. Dynamic monopolies in tori. Discrete applied mathematics, 137(2):197-212, 2004. Google Scholar
  20. F Fogelman, Eric Goles, and Gérard Weisbuch. Transient length in sequential iteration of threshold functions. Discrete Applied Mathematics, 6(1):95-98, 1983. Google Scholar
  21. Silvio Frischknecht, Barbara Keller, and Roger Wattenhofer. Convergence in (social) influence networks. In International Symposium on Distributed Computing, pages 433-446. Springer, 2013. Google Scholar
  22. Juan P Garrahan, Peter Sollich, and Cristina Toninelli. Kinetically constrained models. Dynamical heterogeneities in glasses, colloids, and granular media, 150:111-137, 2011. Google Scholar
  23. Bernd Gärtner and Ahad N Zehmakan. (Biased) Majority Rule Cellular Automata. arXiv preprint, 2017. URL: http://arxiv.org/abs/1711.10920.
  24. Bernd Gärtner and Ahad N Zehmakan. Majority Model on Random Regular Graphs. Latin American Symposium on Theoretical Informatics, pages 572-583, 2018. Google Scholar
  25. Eric Goles and Jorge Olivos. Periodic behaviour of generalized threshold functions. Discrete mathematics, 30(2):187-189, 1980. Google Scholar
  26. Mark Granovetter. Threshold models of collective behavior. American journal of sociology, 83(6):1420-1443, 1978. Google Scholar
  27. Lianna Hambardzumyan, Hamed Hatami, and Yingjie Qian. Polynomial method and graph bootstrap percolation. arXiv preprint, 2017. URL: http://arxiv.org/abs/1708.04640.
  28. Alexander Holroyd et al. The metastability threshold for modified bootstrap percolation in d dimensions. Electronic Journal of Probability, 11:418-433, 2006. Google Scholar
  29. Alexander E Holroyd. Sharp metastability threshold for two-dimensional bootstrap percolation. Probability Theory and Related Fields, 125(2):195-224, 2003. Google Scholar
  30. Nicole Immorlica, Robert Kleinbergt, Brendan Lucier, and Morteza Zadomighaddam. Exponential segregation in a two-dimensional schelling model with tolerant individuals. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 984-993. SIAM, 2017. Google Scholar
  31. Svante Janson, Tomasz Łuczak, Tatyana Turova, Thomas Vallier, et al. Bootstrap percolation on the random graph G_n, p. The Annals of Applied Probability, 22(5):1989-2047, 2012. Google Scholar
  32. Clemens Jeger and Ahad N Zehmakan. Dynamic monopolies in two-way bootstrap percolation. Discrete Applied Mathematics, 2019. Google Scholar
  33. Yashodhan Kanoria, Andrea Montanari, et al. Majority dynamics on trees and the dynamic cavity method. The Annals of Applied Probability, 21(5):1694-1748, 2011. Google Scholar
  34. David Kempe, Jon Kleinberg, and Éva Tardos. Maximizing the spread of influence through a social network. In Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, pages 137-146. ACM, 2003. Google Scholar
  35. Jane Molofsky, Richard Durrett, Jonathan Dushoff, David Griffeath, and Simon Levin. Local frequency dependence and global coexistence. Theoretical population biology, 55(3):270-282, 1999. Google Scholar
  36. Natasha Morrison and Jonathan A Noel. Extremal bounds for bootstrap percolation in the hypercube. Journal of Combinatorial Theory, Series A, 156:61-84, 2018. Google Scholar
  37. Elchanan Mossel, Joe Neeman, and Omer Tamuz. Majority dynamics and aggregation of information in social networks. Autonomous Agents and Multi-Agent Systems, 28(3):408-429, 2014. Google Scholar
  38. Ahad N Zehmakan. Opinion Forming in Erdös-Rényi Random Graph and Expanders. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018. Google Scholar
  39. Hamed Omidvar and Massimo Franceschetti. Self-organized Segregation on the Grid. Journal of Statistical Physics, 170(4):748-783, 2018. Google Scholar
  40. Hamed Omidvar and Massimo Franceschetti. Shape of diffusion and size of monochromatic region of a two-dimensional spin system. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 100-113. ACM, 2018. Google Scholar
  41. David Peleg. Local majority voting, small coalitions and controlling monopolies in graphs: A review. In Proc. of 3rd Colloquium on Structural Information and Communication Complexity, pages 152-169, 1997. Google Scholar
  42. Roberto H Schonmann. Finite size scaling behavior of a biased majority rule cellular automaton. Physica A: Statistical Mechanics and its Applications, 167(3):619-627, 1990. Google Scholar
  43. Roberto H Schonmann. On the behavior of some cellular automata related to bootstrap percolation. The Annals of Probability, pages 174-193, 1992. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact