Discrete Analysis Seminar

A graph G is said to H-percolate if all missing edges can be added eventually by iteratively completing copies of H minus an edge. This process was introduced by Bollobás (1967) and studied more recently by Balogh, Bollobás and Morris (2012) in the case that G is the Erdős–Rényi graph G(n,p). In this talk, we will discuss our recent work with Zsolt Bartha, which locates the critical percolation threshold p_c when H=K_r, answering an open problem of Balogh, Bollobás and Morris. The proof works for all "reasonably balanced" H (such that H-e is 2-balanced for all edges e in H).