Marinissen, Bart (2018) Towards Classifying Bootstrap Percolation on Cayley Graphs. Master's Thesis / Essay, Computing Science.
|
Text
reportFinal.pdf Download (7MB) | Preview |
|
![[img]](https://fse.studenttheses.ub.rug.nl/style/images/fileicons/text.png) |
Text
toestemming.pdf Restricted to Registered users only Download (99kB) |
Abstract
k-threshold bootstrap percolation is a very simple model of infection processes. We study how this model behaves on Cayley-graphs of amenable graphs. This is guided by the conjecture that on these graphs, either complete infection is guaranteed or impossible depending on the threshold k. To this end, we prove this conjecture holds for abelian groups of rank 2. We also find at which k complete infection is guaranteed. These results are essentially an extension of methods used in [Sch92] to prove the conjecture for Cayley-graphs on Z n using canonical generators. Finally, we outline an approach that might extend these results to all Cayley graphs of abelian groups. Moreover, we test the conjecture experimentally on Cayley-graphs of Heisenberg and Lamplighter groups. Here we find evidence that the conjecture holds for the Heisenberg groups. The results for the lamplighter groups are inconclusive. However, we do find a very interesting phenomenon with the lamplighter group. The number of final infected nodes in these graphs seems to cluster around tenths of the total number of nodes in the graph.
| Item Type: | Thesis (Master's Thesis / Essay) |
|---|---|
| Supervisor name: | Renardel de Lavalette, G.R. and Rodrigues Valesin, D. |
| Degree programme: | Computing Science |
| Thesis type: | Master's Thesis / Essay |
| Language: | English |
| Date Deposited: | 11 Apr 2018 |
| Last Modified: | 12 Apr 2018 11:09 |
| URI: | https://fse.studenttheses.ub.rug.nl/id/eprint/16683 |
Actions (login required)
 |
View Item |