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\geq s \geq 3$.
@article{10_37236_8997,
author = {Erhan Bayraktar and Suman Chakraborty},
title = {\(K_{r,s}\) graph bootstrap percolation},
journal = {The electronic journal of combinatorics},
year = {2022},
volume = {29},
number = {1},
doi = {10.37236/8997},
zbl = {1486.05273},
url = {http://geodesic.mathdoc.fr/articles/10.37236/8997/}
}
TY - JOUR
AU - Erhan Bayraktar
AU - Suman Chakraborty
TI - \(K_{r,s}\) graph bootstrap percolation
JO - The electronic journal of combinatorics
PY - 2022
VL - 29
IS - 1
UR - http://geodesic.mathdoc.fr/articles/10.37236/8997/
DO - 10.37236/8997
ID - 10_37236_8997
ER -
