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).
%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
}