Strong-majority bootstrap percolation on regular graphs
| Speaker: | Jim Geelen |
|---|---|
| Affiliation: | University of Waterloo |
| Room: | Mathematics and Computer Building (MC) 6486 |
Abstract:
Consider the following process of dissemination of information over a network. Given a graph, we initially pick a (random) subset of informed vertices called active. Active vertices remain active forever. Moreover, at any stage in the process, an inactive vertex turns active if it has a strong majority of active neighbours. One fundamental problem is to determine whether or not all vertices will eventually become active, depending on the initial set of active vertices. This and many variants of the model with similar dissemination rules have been widely studied in the literature in the context of bootstrap percolation or as a particular case of cellular automata. In this talk, we give an overview of the field, and present some recent results about the strong-majority bootstrap percolation process on a certain family of regular graphs. (This is joint work with Dieter Mitsche and Pawel Pralat.)