Majority bootstrap percolation on the random graph G(n,p)

Majority bootstrap percolation on the random graph $G_{n,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^{\ast }$ of the final active set. The parameters of the model are, besides $n$ (tending to $\mathrm{\infty }$), the size $A(0)=A_0(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)=\theta n$ and every range of $p$ and show that the model exhibits different behaviours for different ranges of $p$. For very small $p \ll \frac{1}{n}$,theactivationdoesnotspreadsignificantly\mathrm{.}Forlarge$p \gg \frac{1}{n}$thenweseeaphasetransitionat$A(0) \simeq \frac{1}{2}n$. In the case $p=\frac{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.