On K₂, t-bootstrap percolation

DOI10.1007/S00373-020-02271-9zbMATH Open1470.05144arXiv1806.10425OpenAlexW3137020372MaRDI QIDQ2045368FDOQ2045368

Authors: Mohammadreza Bidgoli, A. Mohammadian, B. Tayfeh-Rezaie 

Publication date: 12 August 2021

Published in: Graphs and Combinatorics (Search for Journal in Brave)

Abstract: Given two graphs $G$ and $H$, it is said that $G$ percolates in $H$-bootstrap process if one could join all the nonadjacent pairs of vertices of $G$ in some order such that a new copy of $H$ is created at each step. Balogh, Bollob'as and Morris in 2012 investigated the threshold of $H$-bootstrap percolation in the ErdH{o}s-R'enyi model for the complete graph $H$ and proposed the similar problem for $H=K_{s,t}$, the complete bipartite graph. In this paper, we provide lower and upper bounds on the threshold of $K_{2,t}$-bootstrap percolation. In addition, a threshold function is derived for $K_{2,4}$-bootstrap percolation.

Full work available at URL: https://arxiv.org/abs/1806.10425

Recommendations

• Bootstrap percolation on G(n,p) revisited
• Bootstrap percolation and kinetically constrained models on hyperbolic lattices
• Scaling limit and critical exponents for two-dimensional bootstrap percolation
• \(K_{r,s}\) graph bootstrap percolation
• The time of bootstrap percolation in two dimensions
• A sharper threshold for bootstrap percolation in two dimensions
• Bootstrap percolation in random \(k\)-uniform hypergraphs
• Bootstrap percolation on the random graph \(G_{n,p}\)
• Bootstrap percolation on the product of the two-dimensional lattice with a Hamming square
• Bootstrap percolation on the hypercube

zbMATH Keywords

thresholdrandom graphbootstrap percolation

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Interacting random processes; statistical mechanics type models; percolation theory (60K35)

Cites Work

• Threshold functions
• Introduction to Random Graphs
• Title not available (Why is that?)
• Graph bootstrap percolation
• Title not available (Why is that?)
• On the maximum running time in graph bootstrap percolation
• The time of graph bootstrap percolation
• Sharp thresholds for contagious sets in random graphs

Cited In (10)

• Bootstrap percolation and kinetically constrained models on hyperbolic lattices
• On the running time of hypergraph bootstrap percolation
• Weakly saturated random graphs
• \(H\)-percolation with a random \(H\)
• \(K_{r,s}\) graph bootstrap percolation
• Complexity of Two-dimensional Bootstrap Percolation Difficulty: Algorithm and NP-Hardness
• Ore and Chvátal-type degree conditions for bootstrap percolation from small sets
• Polluted bootstrap percolation with threshold two in all dimensions
• Scaling limit and critical exponents for two-dimensional bootstrap percolation
• The time of graph bootstrap percolation

This page was built for publication: On \(K_{2, t}\)-bootstrap percolation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2045368)