Bootstrap Percolation on a Graph with Random and Local Connections

Let be a superposition of the random graph and a one-dimensional lattice: the n vertices are set to be on a ring with fixed edges between the consecutive vertices, and with random independent edges given with probability p between any pair of vertices. Bootstrap percolation on a random graph is a process of spread of "activation" on a given realization of the graph with a given number of initially active nodes. At each step those vertices which have not been active but have at least active neighbours become active as well. We study the size of the final active set in the limit when . The parameters of the model are n, the size of the initially active set and the probability of the edges in the graph. The bootstrap percolation process on was studied earlier. Here we show that the addition of n local connections to the graph leads to a more narrow critical window for the phase transition, preserving however, the critical scaling of parameters known for the model on . We discover a range of parameters which yields percolation on but not on G(n,p).