Linear algebra and bootstrap percolation

DOI10.1016/J.JCTA.2012.03.005MaRDI QIDQ423652zbMATH OpenOpenAlexFDO

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

Publication date 4 June 2012

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

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

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)

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.

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

Cites work

• scientific article; zbMATH DE number 3920492 (Why is no real title available?)
• scientific article; zbMATH DE number 3275275 (Why is no real title available?)
• scientific article; zbMATH DE number 3076934 (Why is no real title available?)
• A sharper threshold for bootstrap percolation in two dimensions
• An extremal problem for sets with applications to graph theory
• An extremal problem for two families of sets
• Bootstrap percolation in high dimensions
• Bootstrap percolation on the hypercube
• Metastability effects in bootstrap percolation
• Random disease on the square grid
• Sharp metastability threshold for two-dimensional bootstrap percolation
• The sharp threshold for bootstrap percolation in all dimensions

Cited in

(23)

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

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)