Strong-majority bootstrap percolation on regular graphs with low dissemination threshold

STOCHASTIC PROCESSES AND THEIR APPLICATIONS

卷:127

Article

Mitsche, Dieter¹  Perez-Gimenez, Xavier²  Pralat, Pawel² 

[1] Univ Nice Sophia Antipolis, Lab JA Dieudonne, Parc Valrose, F-06108 Nice 02, France

[2] Ryerson Univ, Dept Math, Toronto, ON, Canada

关键词: Bootstrap percolation;    Regular graphs;    Strong majority rule;   

DOI  :  10.1016/j.spa.2017.02.001

来源: Elsevier

【 摘 要 】

Consider the following model of strong-majority bootstrap percolation on a graph. Let r >= 1 be some integer, and p is an element of[0, 1]. Initially, every vertex is active with probability p, independently from all other vertices. Then, at every step of the process, each vertex nu of degree deg(nu) becomes active if at least (deg(nu) + 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 et al. (2011). (C) 2017 Elsevier B.V. All rights reserved.

【 授权许可】

Free