2015/03/24 by Stefánsson, Sigurdur Örn, Vallier, Thomas
#FOS: Mathematics #Probability (math.PR)
paper · doi:10.48550/arxiv.1503.07029
Majority bootstrap percolation on the random graph Gn,p is a process of spread of "activation" on a given realisation of the graph with a given number of initially active nodes. At each step those vertices which have more active neighbours than inactive neighbours become active as well. We study the size A^* of the final active set. The parameters of the model are, besides n (tending to ∞), the size A(0)=A0(n) of the initially active set and the probability p=p(n) of the edges in the graph. We prove that the process cannot percolate for A(0) = o(n). We study the process for A(0) = θn and every range of p and show that the model exhibits different behaviours for different ranges of p. For very small p ≪ (1)/(n), the activation does not spread significantly. For large p ≫ (1)/(n) then we see a phase transition at A(0) ≃ (1)/(2)n. In the case p= (c)/(n), the activation propagates to a significantly larger part of the graph but (the process does not percolate) a positive part of the graph remains inactive.