Javascript must be enabled for the correct page display

Towards Classifying Bootstrap Percolation on Cayley Graphs

Marinissen, Bart (2018) Towards Classifying Bootstrap Percolation on Cayley Graphs. Master's Thesis / Essay, Computing Science.


Download (7MB) | Preview
[img] Text
Restricted to Registered users only

Download (99kB)


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

Actions (login required)

View Item View Item