= Monotone threshold activation
{title2=$v\text{ activates when }|N(v)\cap A|\ge t_v$}
In a finite <graph>, start with an active <vertex set> $A_0$ and thresholds $t_v$. An inactive <vertex> becomes active once sufficiently many neighbours are active, and activated <vertices> remain active. Add eligible <vertices> until no more can be added. If $C$ is any threshold-closed <set> containing $A_0$, <induction> shows every activated <vertex> lies in $C$. The terminal active set is itself closed, so it is the least such closure and is independent of the eligible-vertex processing order.
For <integer> thresholds, compute active-neighbour counts and keep a work queue of <vertices> newly reaching their thresholds. Each <vertex> is queued once and each <edge> is inspected a constant number of times, giving $O(|V|+|E|)$ <running time>. Strict-majority activation has $t_v=\lfloor\deg(v)/2\rfloor+1$, so an isolated inactive <vertex> never qualifies. A <maximum priority queue> of activation margins is an alternative implementation.
Back to article page
