Contagious sets in expanders
Tuesday, May 21, 2013
4:00pm 5130 Upson Hall
"We consider the following activation process on undirected $d$-regular
graphs: a vertex is active either if it belongs to a set of initially activated
vertices or if at some point it has at least $r$ active neighbors where $r \leq d$ is the
activation threshold. Such processes are studied in several fields such as
fault tolerant distributed computing, epidemiology, risk analysis,
statistical physics and viral marketing.
A contagious set is a set whose activation results with the entire graph being active.
Our main contribution are new upper bounds on the minimal size of a contagious set
for graphs with expansion properties (parameterized by the spectral gap and by the girth of
the graphs). In some cases, we also provide nearly matching lower bounds.
Our results are algorithmic, entailing simple and efficient algorithms for selecting contagious sets. Several open problems arising from this work will be discussed as well.
Joint work with Amin Coja-Oghlan, Michael Krivelevich and Uri Feige"