Sharp threshold for K₄-percolation

2017/05/24 by Kolesnik, Brett
#Combinatorics (math.CO) #FOS: Mathematics #Probability (math.PR)

paper · doi:10.48550/arxiv.1705.08882

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 \cal G_n,p by iteratively completing copies of K₄ minus an edge. This refines work of Balogh, Bollobás and Morris that bounds the threshold up to multiplicative constants.

Related

• H-percolation with a random H
• Sharp Fuss-Catalan thresholds in graph bootstrap percolation
• K_r,s graph bootstrap percolation
• Percolation Threshold Results on \Erdos-\Renyi Graphs: an Empirical Process Approach
• On K_2,t-bootstrap percolation