 |
Center for Nonlinear Studies |
Bootstrap Percolation is a discrete-time process that models the spread of information or disease across the vertex set of a graph. We consider the following version of this process: Initially, each vertex of the graph is set active with probability p or inactive otherwise. Then, at each time step, every inactive vertex with at least k active neighbors becomes active. Active vertices will always remain active. The process ends when it reaches a stationary state. If all the vertices eventually become active, then we say we achieve percolation. This process has been widely studied on many families of graphs, deterministic and random. We analyze the Bootstrap Percolation process on a Random Geometric Graph. A Random Geometric Graph is obtained by choosing n vertices uniformly at random from the unit d-dimensional cube or torus, and joining any two vertices by an edge if they are within a certain distance, r, of each other. We obtain very precise results that characterize the final state of the Bootstrap Percolation process in terms of the parameters p and r with high probability as the number n of vertices tends to infinity.
Host: Anatoly Zlotnik