Bootstrap percolation with inhibition

Einarsson, Hafsteinn; Lengler, Johannes; Mousset, Frank; Panagiotou, Konstantinos and Steger, Angelika (2019): Bootstrap percolation with inhibition. In: Random Structures & Algorithms, Vol. 55, No. 4: pp. 881-925

Abstract

We study a variant of the classical bootstrap percolation process on Erdos Renyi random graphs. The graphs we consider have inhibitory vertices obstructing the diffusion of activity and excitatory vertices facilitating it. We study both a synchronous and an asynchronous version of the process. Both begin with a small initial set of active vertices, and the activation spreads to all vertices for which the number of excitatory active neighbors exceeds the number of inhibitory active neighbors by a certain amount. We show that in the synchronous process, inhibitory vertices may cause unstable behavior: tiny changes in the size of the starting set can dramatically influence the size of the final active set. We further show that in the asynchronous model the process becomes stable and stops with an active set containing a nontrivial deterministic constant fraction of all vertices. Moreover, we show that percolation occurs significantly faster asynchronously than synchronously.

• Item Type: Journal article
• Faculties: Mathematics, Computer Science and Statistics > Mathematics
• Subjects: 500 Science > 510 Mathematics
• ISSN: 1042-9832
• Language: English