Extremal problems about bootstrap percolation on graphs
| dc.contributor.author | Zhao, Ruoxin | |
| dc.contributor.examiningcommittee | Gunderson, Karen (Mathematics) Kirkland, Stephen (Mathematics) Miller, Avery (Computer Science) | en_US |
| dc.contributor.supervisor | Gunderson, Karen (Mathematics) | en_US |
| dc.date.accessioned | 2021-01-19T22:15:37Z | |
| dc.date.available | 2021-01-19T22:15:37Z | |
| dc.date.copyright | 2021-01-06 | |
| dc.date.issued | 2020-12 | en_US |
| dc.date.submitted | 2021-01-07T02:22:30Z | en_US |
| dc.degree.discipline | Mathematics | en_US |
| dc.degree.level | Master of Mathematical, Computational and Statistical Sciences (M.M.C.S.S.) | en_US |
| dc.description.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. | en_US |
| dc.description.note | February 2021 | en_US |
| dc.identifier.uri | http://hdl.handle.net/1993/35278 | |
| dc.language.iso | eng | en_US |
| dc.rights | open access | en_US |
| dc.subject | Boothstrap percolation | en_US |
| dc.subject | Minimal percolating sets | en_US |
| dc.subject | Minimum percolating set | en_US |
| dc.subject | Regular graphs | en_US |
| dc.subject | Grid graphs | en_US |
| dc.subject | Trees | en_US |
| dc.title | Extremal problems about bootstrap percolation on graphs | en_US |
| dc.type | master thesis | en_US |