Linear algebra and bootstrap percolation

DOI10.1016/J.JCTA.2012.03.005zbMATH Open1242.05190arXiv1107.1410OpenAlexW2148333157MaRDI QIDQ423652FDOQ423652

Robert Morris, Oliver Riordan, József Balogh, Béla Bollobás

Publication date: 4 June 2012

Published in: Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Abstract: In $HH$-bootstrap percolation, a set $AsubsetV(HH)$ of initially 'infected' vertices spreads by infecting vertices which are the only uninfected vertex in an edge of the hypergraph $HH$. A particular case of this is the $H$-bootstrap process, in which $HH$ encodes copies of $H$ in a graph $G$. We find the minimum size of a set $A$ that leads to complete infection when $G$ and $H$ are powers of complete graphs and $HH$ encodes induced copies of $H$ in $G$. The proof uses linear algebra, a technique that is new in bootstrap percolation, although standard in the study of weakly saturated graphs, which are equivalent to (edge) $H$-bootstrap percolation on a complete graph.

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

Recommendations

• Bootstrap percolation in high dimensions
• Probabilistic bootstrap percolation
• Linear systems and determinantal random point fields
• Bootstrap percolation on the hypercube
• scientific article; zbMATH DE number 1747331
• Bootstrap percolation, probabilistic cellular automata and sharpness
• The complexity of the bootstraping percolation and other problems
• BOOTSTRAP PERCOLATION ON RANDOM GEOMETRIC GRAPHS
• Random matrix minor processes related to percolation theory
• Linear maps preserving permutation and stochastic matrices

zbMATH Keywords

linear algebraweak saturationbootstrap percolation

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Interacting random processes; statistical mechanics type models; percolation theory (60K35) Hypergraphs (05C65)

Cites Work

• Title not available (Why is that?)
• An extremal problem for two families of sets
• Sharp metastability threshold for two-dimensional bootstrap percolation
• Metastability effects in bootstrap percolation
• A sharper threshold for bootstrap percolation in two dimensions
• Bootstrap Percolation in High Dimensions
• The sharp threshold for bootstrap percolation in all dimensions
• Bootstrap percolation on the hypercube
• Random disease on the square grid
• Title not available (Why is that?)
• An extremal problem for sets with applications to graph theory
• Title not available (Why is that?)

Cited In (23)

• Extremal bounds for bootstrap percolation in the hypercube
• Exact bounds for some hypergraph saturation problems
• Graph bootstrap percolation
• Percolating sets in bootstrap percolation on the Hamming graphs and triangular graphs
• The minimum number of clique-saturating edges
• Minimum degree conditions for small percolating sets in bootstrap percolation
• Weak saturation numbers of complete bipartite graphs in the clique
• Minimizing the Number of Edges in $K_{(s,t)}$-Saturated Bipartite Graphs
• Maximal Spanning Time for Neighborhood Growth on the Hamming Plane
• On the running time of hypergraph bootstrap percolation
• Weak saturation stability
• On the number of \(K_4\)-saturating edges
• Bootstrap percolation on the random graph \(G_{n,p}\)
• Transitive closure in a polluted environment
• Neighborhood growth dynamics on the Hamming plane
• Lower bounds for graph bootstrap percolation via properties of polynomials
• \(K_{s,t}\)-saturated bipartite graphs
• Saturation in the Hypercube and Bootstrap Percolation
• Weakly saturated hypergraphs and a conjecture of Tuza
• Extremal bounds for bootstrap percolation in the hypercube
• A sharp threshold for bootstrap percolation in a random hypergraph
• Phylogeny numbers of generalized Hamming graphs
• On the maximum running time in graph bootstrap percolation

This page was built for publication: Linear algebra and bootstrap percolation

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