Contagious sets in expanders

 

 

Daniel Reichman

Tuesday, May 21, 2013
4:00pm 5130
Upson Hall

 

Abstract:

"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"