Critical Probability of Multi-State Bootstrap Percolation on Random Graphs 

We show the critical connection probability for spread of bootstrap percolation with threshold 2 on random graphs is \Theta(1/\sqrt{n}). We discuss the extension to general threshold k and a conjecture for multi-state bootstrap percolations with thresholds k_1 and k_2.