Sharp threshold for K4-percolation

Seminar | September 6 | 3:10-4 p.m. | 1011 Evans Hall

 Brett Kolesnik, UC Berkeley

 Department of Statistics

Graph bootstrap percolation is a cellular automaton introduced by Bollobas. Let H be a graph. Edges are added to an initial graph G=(V,E) if they are in a copy of H minus an edge, until no further edges can be added. If eventually the complete graph on V is obtained, G is said to H-percolate. We identify the sharp threshold for K4-percolation on the Erdos-Renyi graph G(n,p). This improves a result of Balogh, Bollobas and Morris, which bounds the threshold up to multiplicative constants. Based in part on joint works with Omer Angel.