Largest minimal percolating sets in hypercubes under 2-bootstrap percolation

MaRDI QIDQ976739zbMATH OpenFDO

Authors Eric Riedl

Publication date 16 June 2010

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://eudml.org/doc/226637, http://www.emis.de/journals/EJC/Volume_17/Abstracts/v17i1r80.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Interacting random processes; statistical mechanics type models; percolation theory (60K35)

Review text

Summary: Consider the following process, known as \(r\)-bootstrap percolation, on a graph \(G\). Designate some initial infected set \(A\) and infect any vertex with at least \(r\) infected neighbors, continuing until no new vertices can be infected. We say \(A\) percolates if it eventually infects the entire graph. We say \(A\) is a minimal percolating set if \(A\) percolates, but no proper subset percolates. We compute the size of a largest minimal percolating set for \(r= 2\) in the \(n\)-dimensional hypercube.

Recommendations

• Extremal bounds for bootstrap percolation in the hypercube
• Extremal bounds for bootstrap percolation in the hypercube
• Maximal percolation time in hypercubes under 2-bootstrap percolation
• Maximal induced paths and minimal percolating sets in hypercubes
• Minimal percolating sets in bootstrap percolation

Cited in

(28)

• Minimal percolating sets in bootstrap percolation
• Maximal bootstrap percolation time on the hypercube via generalised snake-in-the-box
• Neighborhood growth dynamics on the Hamming plane
• The maximum time of 2-neighbor bootstrap percolation: complexity results
• A cube dismantling problem related to bootstrap percolation
• On the \(P_3\)-hull number of Kneser graphs
• On the spread of influence in graphs
• Lower bounds for graph bootstrap percolation via properties of polynomials
• Minimum degree conditions for small percolating sets in bootstrap percolation
• Percolating sets in bootstrap percolation on the Hamming graphs and triangular graphs
• The maximum time of 2-neighbour bootstrap percolation: algorithmic aspects
• Dynamic monopolies in two-way bootstrap percolation
• The maximum time of 2-neighbour bootstrap percolation in grid graphs and parametrized results
• The Maximum Time of 2-Neighbour Bootstrap Percolation: Complexity Results
• Maximal induced paths and minimal percolating sets in hypercubes
• The time of bootstrap percolation with dense initial sets for all thresholds
• On slowly percolating sets of minimal size in bootstrap percolation
• The time of bootstrap percolation with dense initial sets
• Largest and smallest minimal percolating sets in trees
• Maximal percolation time in hypercubes under 2-bootstrap percolation
• Bootstrap Percolation on Degenerate Graphs
• Rumor spreading: A trigger for proliferation or fading away
• On the maximum running time in graph bootstrap percolation
• Saturation in the hypercube and bootstrap percolation
• Extremal bounds for bootstrap percolation in the hypercube
• Extremal bounds for bootstrap percolation in the hypercube
• Target set selection with maximum activation time
• Minimum lethal sets in grids and tori under 3-neighbour bootstrap percolation

This page was built for publication: Largest minimal percolating sets in hypercubes under 2-bootstrap percolation

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