\(K_{r,s}\) graph bootstrap percolation (Q2121788)

Summary: A graph \(G\) percolates in the \(K_{r,s}\)-bootstrap process if we can add all missing edges of \(G\) in some order such that each edge creates a new copy of \(K_{r,s}\), where \(K_{r,s}\) is the complete bipartite graph. We study \(K_{r,s}\)-bootstrap percolation on the Erdős-Rényi random graph, and determine the percolation threshold for balanced \(K_{r,s}\) up to a logarithmic factor. This partially answers a question raised by \textit{J. Balogh} et al. [Random Struct. Algorithms 41, No. 4, 413--440 (2012; Zbl 1279.68243)]. We also establish a general lower bound of the percolation threshold for all \(K_{r,s}\), with \(r\geqslant s \geqslant 3\).