High-dimensional bootstrap processes in evolving simplicial complexes

Abstract

We study bootstrap percolation processes on random simplicial complexes of some fixed dimension $d\ge 3$. Starting from a single simplex of dimension $d$, we build our complex dynamically in the following fashion. We introduce new vertices one by one, all equipped with a random weight from a fixed distribution $\mu$. The newly arriving vertex selects an existing $(d-1)$-dimensional face at random, with probability proportional to some positive and symmetric function $f$ of the weights of its vertices, and attaches to it by forming a $d$-dimensional simplex. After a complex on $n$ vertices is constructed, we infect every vertex independently at random with some probability $p=p(n)$. Then, in consecutive rounds, we infect every healthy vertex the neighbourhood of which contains at least $r$ disjoint $(k-1)$-dimensional, fully infected faces. Using a reduction to the generalised Pólya urn schemes, we determine the value of critical probability $p_c=p_c(n;\mu ,f)$, such that if $p\gg p_c$ then, with probability tending to 1 as $n\to \infty$, the infection spreads to the whole vertex set of the complex, while if $p\ll p_c$ then the infection process stops with healthy vertices remaining in the complex.

25 pages

References in corpus (1)

• Self-similar disk packings as model spatial scale-free networks