Contagious Sets in Expanders

We consider the following activation process in undirected 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 > 1 is the activation threshold. A contagious set is a set whose activation results with the entire graph being active. Given a graph G, let m ( G, r ) be the minimal size of a contagious set. It is known that for every d -regular or nearly d -regular graph on n vertices, . We consider such graphs that additionally have expansion properties, parameterized by the spectral gap and/or the girth of the graphs. The general flavor of our results is that sufficiently strong expansion properties imply that (and more generally, . In addition, we demonstrate that rather weak assumptions on the girth and/or the spectral gap suffice in order to imply that. For example, we show this for graphs of girth at least 7, and for graphs with λ( G ) < (1 − ε ) d, provided the graph has no 4-cycles. Our results are algorithmic, entailing simple and effcient algorithms for selecting contagious sets.

Authors

• Amin Coja-Oghlan
• Uriel Feige
• Michael Krivelevich
• Daniel Reichman 0001

Keywords

No keywords are indexed for this paper.