New ordering methods to construct contagious sets and induced degenerate subgraphs

DOI10.2140/INVOLVE.2023.16.59zbMath1512.05228OpenAlexW4365503115MaRDI QIDQ6102104

Connor C. Anderson, Akshaj Balasubramanian, Gábor N. Sárközy, Daniel Reichman, Henry Poskanzer

Publication date: 8 May 2023

Published in: Involve (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.2140/involve.2023.16.59

zbMATH Keywords

degenerate subgraphscontagious sets

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Permutations, words, matrices (05A05) Distance in graphs (05C12) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Cites Work

• Combinatorial model and bounds for target set selection
• New bounds for contagious sets
• Largest and smallest minimal percolating sets in trees
• Bootstrap percolation on the random graph \(G_{n,p}\)
• Large induced degenerate subgraphs
• On the behavior of some cellular automata related to bootstrap percolation
• Contagious sets in random graphs
• Proof of Straley's argument for bootstrap percolation.
• Graph bootstrap percolation
• The time of bootstrap percolation with dense initial sets for all thresholds
• On the Approximability of Influence in Social Networks
• Random disease on the square grid
• The sharp threshold for bootstrap percolation in all dimensions
• On generalized graphs
• Extremal bounds for bootstrap percolation in the hypercube

This page was built for publication: New ordering methods to construct contagious sets and induced degenerate subgraphs