Sharp threshold for $K_4$-percolation

Abstract

We locate the critical threshold $p_c$ at which it becomes likely that the complete graph $K_n$ can be obtained from the Erdős-Rényi graph ${\mathcal{G}}_{n,p}$ by iteratively completing copies of $K_4$ minus an edge. This refines work of Balogh, Bollobás and Morris that bounds the threshold up to multiplicative constants.

Exposition improved; results unchanged

References in corpus (2)

• Thresholds for contagious sets in random graphs
• Large deviations for subcritical bootstrap percolation on the random graph

Cited by in corpus (2)

• Weakly saturated random graphs
• Transitive closure in a polluted environment