On the Maximum Running Time in Graph Bootstrap Percolation

[摘要] Graph bootstrap percolation is a simple cellular automaton introduced by Bollobás in 1968. Given a graph $H$ and a set $G \subseteq E(K_n)$ we initially `infect' all edges in $G$ and then, in consecutive steps, we infect every $e \in K_n$ that completes a

[学科分类] 离散数学和组合数学

[关键词] Bootstrap percolation;Weak saturation;Cellular automata;Monotone cellular automata;Extremal combinatorics