Leaps in long-range connectivity

Advancing the mathematical theory of bootstrap percolation, where active cells on a lattice with few active neighbours cease to be active.

Bootstrap percolation originated as a simple cellular automata model of the spread of infection. Given a set of initially infected sites, in consecutive rounds sites become infected if they satisfy a certain infection rule, for example, more than a given number of their neighbours are infected. Percolation occurs if every node is eventually infected.

In this project we investigate the typical and extremal properties of bootstrap percolation for various infection rules and underlying networks. For sites that are initially randomly infected, we study the critical density of infection that leads to percolation. Alternatively, if the initial infected sites are set by hand, we study how many infected nodes are necessary to infect the whole network.

Bootstrap percolation can be used to model many real-life phenomena, such as pandemics, computer network failure, ferromagnetic behaviour, the spread of voting preferences and information processing in neural networks. A better mathematical theory will help us understand these processes and draw reliable conclusions well beyond what can be achieved through computer simulations.

Leaps in long-range connectivity

Related papers

Emergence of strongly connected components in continuum disk-spin percolation

F. Caravelli, M. Bardoscia, F. Caccioli

Journal of Statistical Mechanics: Theory and Experiment

Subcritical U-Bootstrap percolation models have non-trivial phase transitions

P. Balister, B. Bollobas, M. Przykucki, P. Smith

Transactions of the American Mathematical Society

Maximum percolation time in two-dimensional bootstrap percolation

F. Benevides, M. Przykucki

SIAM Journal on Discrete Mathematics

Bootstrap percolation on Galton–Watson trees

B. Bollobas, K. Gunderson, C. Janson, M. Przykucki

Electronic Journal of Probability

See related papers >