Mathematics Colloquia and Seminars
Large deviations for bootstrap percolation on the random graphMathematical Physics & Probability
|Speaker:||Brett Kolesnik, UC Berkeley|
|Start time:||Wed, Apr 18 2018, 4:10PM|
In r-neighbour bootstrap percolation, vertices in a graph are activated if they have at least r active neighbours. Using Guseinov’s discrete calculus of variations, we identify the large deviations rate function for the event that a small set of vertices activates atypically many vertices in the Erdos–Renyi graph G(n,p). This leads to estimates for the size of the smallest sets that activate the entire graph. As another application, we find the sharp threshold for K4-percolation on G(n,p), at which point the complete graph Kn can be obtained from G(n,p) by successively completing copies of K4 minus a single edge. This solves a problem of Balogh, Bollobas and Morris. Joint work with Omer Angel.