Bootstrap percolation in random geometric graphs

DOI10.1017/APR.2023.5MaRDI QIDQ6198069zbMATH OpenOpenAlexFDO

Authors Victor Falgas-Ravry, Amites Sarkar

Publication date 20 February 2024

Published in Advances in Applied Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2110.12166

zbMATH Keywords

random processesbootstrap percolationrandom geometric graphs

Mathematics Subject Classification ID

Point processes (e.g., Poisson, Cox, Hawkes processes) (60G55) Geometric probability and stochastic geometry (60D05) Interacting random processes; statistical mechanics type models; percolation theory (60K35)

Abstract: 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 $alogn$ for some fixed $a>1$. Each vertex is added with probability $p$ to a set $A_0$ of initially infected vertices. Vertices subsequently become infected if they have at least $hetaalogn$ infected neighbours. Here $p,hetain[0,1]$ are taken to be fixed constants. We show that if $heta<(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 $heta>(1+p)/2$, even if one adversarially infects every vertex inside a ball of radius $O(sqrtlogn)$, 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,heta)$ 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.

Recommendations

• Bootstrap percolation on random geometric graphs (extended abstract)
• Bootstrap percolation and the geometry of complex networks
• BOOTSTRAP PERCOLATION ON RANDOM GEOMETRIC GRAPHS
• Bootstrap percolation on geometric inhomogeneous random graphs
• Bootstrap percolation on \(G(n,p)\) revisited

Cites work

• scientific article; zbMATH DE number 227027 (Why is no real title available?)
• scientific article; zbMATH DE number 5066400 (Why is no real title available?)
• A clustering procedure based on the comparison between the \(k\) nearest neighbors graph and the minimal spanning tree.
• A critical constant for the k nearest-neighbour model
• A modified bootstrap percolation on a random graph coupled with a lattice
• A phase transition regarding the evolution of bootstrap processes in inhomogeneous random graphs
• BOOTSTRAP PERCOLATION ON RANDOM GEOMETRIC GRAPHS
• Bootstrap percolation and the geometry of complex networks
• Bootstrap percolation in living neural networks
• Bootstrap percolation in power-law random graphs
• Bootstrap percolation on Galton-Watson trees
• Bootstrap percolation on geometric inhomogeneous random graphs
• Bootstrap percolation on products of cycles and complete graphs
• Bootstrap percolation on the random graph \(G_{n,p}\)
• Bootstrap percolation on the random regular graph
• Bootstrap percolation with inhibition
• Connectivity of random k-nearest-neighbour graphs
• Continuum Percolation
• Edge-isoperimetric inequalities in the grid
• Irreversible \(k\)-threshold processes: Graph-theoretical threshold models of the spread of disease and of opinion
• Metastability effects in bootstrap percolation
• On percolation in random graphs with given vertex degrees
• Percolation
• Random Geometric Graphs
• Random Plane Networks
• Sharp metastability threshold for two-dimensional bootstrap percolation
• Sharpness in the \(k\)-nearest-neighbours random geometric graph model
• The longest edge of the random minimal spanning tree
• The sharp threshold for bootstrap percolation in all dimensions
• Two moments suffice for Poisson approximations: The Chen-Stein method

This page was built for publication: Bootstrap percolation in random geometric graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6198069)