Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
10331118 | Information Processing Letters | 2014 | 5 Pages |
Abstract
In the strict Majority Bootstrap Percolation process each passive vertex v becomes active if at least âdeg(v)+12â of its neighbors are active (and thereafter never changes its state). We address the problem of finding graphs for which a small proportion of initial active vertices is likely to eventually make all vertices active. We study the problem on a ring of n vertices augmented with a “central” vertex u. Each vertex in the ring, besides being connected to u, is connected to its r closest neighbors to the left and to the right. We prove that if vertices are initially active with probability p>1/4 then, for large values of r, percolation occurs with probability arbitrarily close to 1 as nââ. Also, if p<1/4, then the probability of percolation is bounded away from 1.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
M. Kiwi, P. Moisset de Espanés, I. Rapaport, S. Rica, G. Theyssier,