$K_{r,s}$ graph bootstrap percolation

Abstract

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 Balogh, Bollobás, and Morris. We also establish a general lower bound of the percolation threshold for all $K_{r,s}$, with $r\ge s\ge 3$.

14 pages, to appear in the Electronic Journal of Combinatorics