Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

Large deviations for bootstrap percolation on the random graph

Probability

Speaker: Brett Kolesnik, UC Berkeley
Location: 2112 MSB
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.