Extremal problems about bootstrap percolation on graphs
Date
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Bootstrap percolation is a dynamic process on configurations of two possible states of vertices in a graph. For a given graph and a fixed non-negative integer threshold, some vertices are initially "activated" whilst others are "inactivated". At each step, every inactivated vertex will become activated if the number of their activated neighbours is at least the threshold. If all the vertices are eventually activated, then say the set of initially activated vertices percolates. In this thesis, I focus on percolating sets containing as few vertices as possible - minimal and minimum percolating sets. Specifically, I survey exact and approximate cardinalities of minimal/minimum percolating sets of some classes of graphs, and obtain several new bounds and constructions for them. The main tools used in the thesis are structural properties and invariants of graphs. Throughout the thesis, I also present the major outstanding new problems in this area.