Bootstrap percolation with inhibition

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...

Full description

Saved in:
Bibliographic Details
Published in:Random structures & algorithms 2019-12, Vol.55 (4), p.881-925
Main Authors: Einarsson, Hafsteinn, Lengler, Johannes, Mousset, Frank, Panagiotou, Konstantinos, Steger, Angelika
Format: Article
Language:English
Subjects:
Apexes
Blocking
bootstrap percolation
Graphs
input normalization
Percolation
random graphs
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:1042-9832
1098-2418
DOI:10.1002/rsa.20854