Weakly saturated random graphs

Abstract

As introduced by Bollobás, a graph $G$ is weakly $H$-saturated if the complete graph $K_n$ is obtained by iteratively completing copies of $H$ minus an edge. For all graphs $H$, we obtain an asymptotic lower bound for the critical threshold $p_c$, at which point the Erdős--Rényi graph ${\mathcal{G}}_{n,p}$ is likely to be weakly $H$-saturated. We also prove an upper bound for $p_c$, for all $H$ which are, in a sense, strictly balanced. In particular, we improve the upper bound by Balogh, Bollob{á}s and Morris for $H=K_r$, and we conjecture that this is sharp up to constants.

References in corpus (4)

• Extremal results for random discrete structures
• Thresholds for contagious sets in random graphs
• Large deviations for subcritical bootstrap percolation on the random graph
• Sharp threshold for $K_4$-percolation

Cited by in corpus (1)

• $H$-percolation with a random $H$