$H$-percolation with a random $H$

Abstract

In $H$-percolation, we start with an Erdős--Rényi graph ${\mathcal{G}}_{n,p}$ and then iteratively add edges that complete copies of $H$. The process percolates if all edges missing from ${\mathcal{G}}_{n,p}$ are eventually added. We find the critical threshold $p_c$ when $H={\mathcal{G}}_{k,1/2}$ is uniformly random, solving a problem of Balogh, Bollobás and Morris.

References in corpus (1)

• Weakly saturated random graphs