New bounds for contagious sets

DOI10.1016/J.DISC.2012.01.016zbMATH Open1242.05265OpenAlexW1999279606MaRDI QIDQ418891FDOQ418891

Authors: Daniel Reichman 

Publication date: 30 May 2012

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disc.2012.01.016

Recommendations

• Contagious sets in random graphs
• Contagious sets in expanders
• Triggering cascades on strongly connected directed graphs

zbMATH Keywords

bootstrap percolation\(d\)-degenerate graphs

Mathematics Subject Classification ID

Interacting random processes; statistical mechanics type models; percolation theory (60K35) Vertex degrees (05C07) Graph theory (05C99)

Cites Work

• Large induced degenerate subgraphs
• Lower bounds on the independence number in terms of the degrees
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• On the approximability of influence in social networks
• Combinatorial model and bounds for target set selection
• Title not available (Why is that?)
• Cascading behavior in networks: algorithmic and economic issues
• The sharp threshold for bootstrap percolation in all dimensions
• Bootstrap percolation on the random graph \(G_{n,p}\)
• Bootstrap percolation on the hypercube
• Bootstrap percolation in three dimensions
• Bootstrap Percolation on Infinite Trees and Non-Amenable Groups
• Majority Bootstrap Percolation on the Hypercube
• Random disease on the square grid
• On the size of identifying codes in binary hypercubes
• Bootstrap percolation on the random regular graph

Cited In (20)

• Infinite and Giant Components in the Layers Percolation Model
• The acquaintance time of (percolated) random geometric graphs
• Hierarchical cycle-tree packing model for optimal \(K\)-core attack
• Constant thresholds can make target set selection tractable
• Acquaintance time of random graphs near connectivity threshold
• Minimum degree conditions for small percolating sets in bootstrap percolation
• On some tractable and hard instances for partial incentives and target set selection
• Contagious sets in expanders
• Bounds and extremal graphs for degenerate subsets, dynamic monopolies, and partial incentives
• Contagious sets in random graphs
• On giant components and treewidth in the layers model
• Deterministic bootstrap percolation on trees
• A note on the acquaintance time of random graphs
• On the spread of influence in graphs
• Hardness Results for Seeding Complex Contagion with Neighborhoods
• On the complexity of reasoning about opinion diffusion under majority dynamics
• New ordering methods to construct contagious sets and induced degenerate subgraphs
• Triggering cascades on strongly connected directed graphs
• Minimal contagious sets in random regular graphs
• Dynamic monopolies for degree proportional thresholds in connected graphs of girth at least five and trees

This page was built for publication: New bounds for contagious sets

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