Bootstrap percolation with inhibition. Issue 4 (16th April 2019)

• Record Type: Journal Article
• Authors: Einarsson, Hafsteinn; Lengler, Johannes; Mousset, Frank; Panagiotou, Konstantinos; Steger, Angelika
• Is Part Of: Random structures & algorithms. Volume 55:Issue 4(2019)
• Page Start: 881
• Page End: 925
• Publication Date: 2019-04-16
• Subjects: bootstrap percolation -- input normalization -- random graphs; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20854
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract : We study a variant of the classical bootstrap percolation process on Erdős Rényi 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.