On K_2,t-bootstrap percolation

2018/06/27 by Mohammadreza Bidgoli, Bidgoli, M. R., Ali Mohammadian +3
Mathematics · #05C80 #60K35 #Combinatorics (math.CO) #FOS: Mathematics #Markov Chains and Monte Carlo Methods #Random Matrices and Applications #Stochastic processes and statistical mechanics

paper · pdf · doi:10.48550/arxiv.1806.10425

openalex publication_date 2018/06/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Given two graphs G and H, it is said that G percolates in H-bootstrap process if one could join all the nonadjacent pairs of vertices of G in some order such that a new copy of H is created at each step. Balogh, Bollobás and Morris in 2012 investigated the threshold of H-bootstrap percolation in the Erdős-Rényi model for the complete graph H and proposed the similar problem for H=K_s,t, the complete bipartite graph. In this paper, we provide lower and upper bounds on the threshold of K_{2, t}-bootstrap percolation. In addition, a threshold function is derived for K_{2, 4}-bootstrap percolation.

Related

• K_r,s graph bootstrap percolation
• Graph bootstrap percolation
• Sharp Fuss-Catalan thresholds in graph bootstrap percolation
• Thresholds for contagious sets in random graphs
• Majority Bootstrap Percolation on G(n,p)