Umeå University's logo

umu.sePublications
System disruptions
There are recurring service disruptions on some of the search portals due to high traffic. We are working to resolve the issue, you may temporarily encounter an error message.
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Bootstrap percolation in random geometric graphs
Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.ORCID iD: 0000-0001-8631-4745
Western Washington University, United States.
2023 (English)In: Advances in Applied Probability, ISSN 0001-8678, E-ISSN 1475-6064, Vol. 55, no 4, p. 1254-1300Article in journal (Refereed) Published
Abstract [en]

Following Bradonji´c and Saniee, we study a model of bootstrap percolation on the Gilbert random geometric graph on the 2-dimensional torus. In this model, the expected number of vertices of the graph is n, and the expected degree of a vertex is a log n for some fixed a>1. Each vertex is added with probability p to a set A0 of initially infected vertices. Vertices subsequently become infected if they have at least θa log n infected neighbours. Here p, θ ∈ [0, 1] are taken to be fixed constants.

We show that if θ <(1+p)/2, then a sufficiently large local outbreak leads with high probability to the infection spreading globally, with all but o(n) vertices eventually becoming infected. On the other hand, for θ >(1+p)/2, even if one adversarially infects every vertex inside a ball of radius O(√log n), with high probability the infection will spread to only o(n) vertices beyond those that were initially infected.

In addition we give some bounds on the (a, p, θ) regions ensuring the emergence of large local outbreaks or the existence of islands of vertices that never become infected. We also give a complete picture of the (surprisingly complex) behaviour of the analogous 1-dimensional bootstrap percolation model on the circle. Finally we raise a number of problems, and in particular make a conjecture on an ‘almost no percolation or almost full percolation’ dichotomy which may be of independent interest.

Place, publisher, year, edition, pages
Cambridge University Press, 2023. Vol. 55, no 4, p. 1254-1300
Keywords [en]
bootstrap percolation, random geometric graphs, random processes
National Category
Probability Theory and Statistics
Identifiers
URN: urn:nbn:se:umu:diva-211166DOI: 10.1017/apr.2023.5ISI: 001168005000008Scopus ID: 2-s2.0-85162047124OAI: oai:DiVA.org:umu-211166DiVA, id: diva2:1779435
Funder
Swedish Research Council, 2016-03488Swedish Research Council, 2021-03687The Swedish Foundation for International Cooperation in Research and Higher Education (STINT), IB 2017-7360Available from: 2023-07-04 Created: 2023-07-04 Last updated: 2025-04-24Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Authority records

Falgas-Ravry, Victor

Search in DiVA

By author/editor
Falgas-Ravry, Victor
By organisation
Department of Mathematics and Mathematical Statistics
In the same journal
Advances in Applied Probability
Probability Theory and Statistics

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 387 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf