\input zb-basic
\input zb-ioport
\iteman{io-port 05997046}
\itemau{Chang, Ching-Lueh; Lyuu, Yuh-Dauh}
\itemti{Stable sets of threshold-based cascades on the Erd\H{o}s-R\'enyi random graphs.}
\itemso{Iliopoulos, Costas S. (ed.) et al., Combinatorial algorithms. 22nd international workshop, IWOCA 2011, Victoria, BC, Canada, July 20--22, 2011. Revised selected papers. Berlin: Springer (ISBN 978-3-642-25010-1/pbk). Lecture Notes in Computer Science 7056, 96-105 (2011).}
\itemab
Summary: Consider the following reversible cascade on the Erd\H{o}s-R\'enyi random graph $G(n,p)$. In round zero, a set of vertices, called the seeds, are active. For a given $\rho \in ( 0,1 ]$, a non-isolated vertex is activated (resp., deactivated) in round $t \in \Bbb Z^{ + }$ if the fraction $f$ of its neighboring vertices that were active in round $t - 1$ satisfies $f \geq \rho $ (resp., $f < \rho )$. An irreversible cascade is defined similarly except that active vertices cannot be deactivated. A set of vertices, $S$, is said to be stable if no vertex will ever change its state, from active to inactive or vice versa, once the set of active vertices equals $S$. For both the reversible and the irreversible cascades, we show that for any constant $\epsilon > 0$, all $p \in [ (1 + \epsilon ) (\ln (e/\rho ))/n,1 ]$ and with probability $1 - n ^{ - \Omega (1)}$, every stable set of $G(n,p)$ has size $O(\lceil \rho n\rceil )$ or $n - O(\lceil \rho n\rceil )$.
\itemrv{~}
\itemcc{}
\itemut{}
\itemli{doi:10.1007/978-3-642-25011-8\_8}
\end