K_r,s graph bootstrap percolation

2019/04/29 by Erhan Bayraktar, Suman Chakraborty, Bayraktar, Erhan +1
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #Markov Chains and Monte Carlo Methods #Probability (math.PR) #Random Matrices and Applications #Stochastic processes and statistical mechanics

paper · pdf · doi:10.48550/arxiv.1904.12764

openalex publication_date 2019/04/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/04

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≥ s ≥ 3.

Related

• On K_2,t-bootstrap percolation
• Graph bootstrap percolation
• Sharp Fuss-Catalan thresholds in graph bootstrap percolation
• H-percolation with a random H
• Majority Bootstrap Percolation on G(n,p)