%0 Generic %1 Mitsche2015Strongmajority %A Mitsche, Dieter %A Pérez-Giménez, Xavier %A Prałat, Paweł %D 2015 %K majority-vote, preprint percolation bootstrap %T Strong-majority bootstrap percolation on regular graphs with low dissemination threshold %U http://arxiv.org/abs/1503.08310 %X Consider the following model of strong-majority bootstrap percolation on a graph. Let r be some positive integer, and p in 0,1. Initially, every vertex is active with probability p, independently from all other vertices. Then, at every step of the process, each vertex v of degree deg(v) becomes active if at least (deg(v)+r)/2 of its neighbours are active. Given any arbitrarily small p>0 and any integer r, we construct a family of d=d(p,r)-regular graphs such that with high probability all vertices become active in the end. In particular, the case r=1 answers a question and disproves a conjecture of Rapaport, Suchan, Todinca, and Verstraete (Algorithmica, 2011).

@misc{Mitsche2015Strongmajority, abstract = {{Consider the following model of strong-majority bootstrap percolation on a graph. Let r be some positive integer, and p in [0,1]. Initially, every vertex is active with probability p, independently from all other vertices. Then, at every step of the process, each vertex v of degree deg(v) becomes active if at least (deg(v)+r)/2 of its neighbours are active. Given any arbitrarily small p\>0 and any integer r, we construct a family of d=d(p,r)-regular graphs such that with high probability all vertices become active in the end. In particular, the case r=1 answers a question and disproves a conjecture of Rapaport, Suchan, Todinca, and Verstraete (Algorithmica, 2011).}}, added-at = {2019-06-10T14:53:09.000+0200}, archiveprefix = {arXiv}, author = {Mitsche, Dieter and P\'{e}rez-Gim\'{e}nez, Xavier and Pra{\l}at, Pawe{\l}}, biburl = {https://www.bibsonomy.org/bibtex/24c632003da0d4f08564b03078a3fa31c/nonancourt}, citeulike-article-id = {13578661}, citeulike-linkout-0 = {http://arxiv.org/abs/1503.08310}, citeulike-linkout-1 = {http://arxiv.org/pdf/1503.08310}, day = 28, eprint = {1503.08310}, interhash = {772e02af8ed544748d628d7b5ce991f2}, intrahash = {4c632003da0d4f08564b03078a3fa31c}, keywords = {majority-vote, preprint percolation bootstrap}, month = mar, posted-at = {2015-04-10 12:28:11}, priority = {2}, timestamp = {2019-08-23T10:58:50.000+0200}, title = {{Strong-majority bootstrap percolation on regular graphs with low dissemination threshold}}, url = {http://arxiv.org/abs/1503.08310}, year = 2015 }