Speaker: Michael Krivelevich, Tel Aviv University
Title:   Contagious sets in random graphs

                    ABSTRACT

Given a graph G and a positive integer r (the so-called threshold
parameter), consider the following activation process in undirected
graphs: a vertex of G 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. A contagious set is a set of vertices in G whose
activation results with the entire graph being active. This scenario,
frequently also called bootstrap percolation, has been extensively
studied in the literature, both theoretical and applied.

Let m(G,r) be the minimal size of a contagious set in G, for
the threshold r. We study the typical value of m(G,r) in binomial
random graphs G(n,p). We discover in particular that choosing
an initial set cleverly is somewhat more beneficial than placing it
at random, as usually considered in the bootstrap percolation
literature. We also find the minimal probability p(n) for having
m(G,r)=r typically.

A joint work with Uriel Feige and Daniel Reichman.