\(K_{r,s}\) graph bootstrap percolation (Q2121788)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | \(K_{r,s}\) graph bootstrap percolation |
scientific article |
Statements
\(K_{r,s}\) graph bootstrap percolation (English)
0 references
4 April 2022
0 references
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\).
0 references
bootstrap percolation
0 references
weak saturation
0 references