Bootstrap percolation of extension hypergraphs

Abstract

For $k$-graphs $F$ and $H_0$ the $F$-bootstrap percolation process (or $F$-process) starting with $H_0$ is a sequence $(H_i{)}_{i\ge 0}$ of $k$-graphs such that $H_{i+1}$ is obtained from $H_i$ by adding all those $e\in V(H_0{)}^{(k)}\setminus E(H_i)$ as edges that complete a new copy of $F$. The running time of this $F$-process, denoted by $M_F(H_0)$, is the smallest $i$ with $H_i=H_{i+1}$. Bollobás proposed the problem of determining the maximum running time for $n\in \mathbb{N}$, i.e., $$M_F(n)=\underset{|V(H_0)|=n}{\max }{M}_F(H_0).$$ Recently, Noel and Ranganathan initiated the study of this quantity for $k$-graphs. In this work, we determine the asymptotics of $M_F(n)$ for a large class of $k$-graphs. Given a graph $G=(V,E)$, the $k$-extension of $G$ is a $k$-graph $F^{(k)}(G)$ obtained from $G$ by enlarging each edge with a $(k-2)$-set of new vertices. We show that for every graph $G$ on $t$ vertices and every $k\ge 3$, $M_{F^{(k)}(G)}(n)\le C_{k,t}$ for some constant $C_{k,t}$ depending only on $t$ and $k$.

13 pages