*********************************** * Princeton Discrete Math Seminar * *********************************** Speaker: Daniel Reichman, Princeton Thursday 4th April, 3:00 in Fine Hall 224. Title: Contagious sets in bootstrap percolation 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. This process (commonly referred to as bootstrap percolation) has been studied in several fields including combinatorics, computer science, statistical physics and viral marketing. 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. I will survey upper and lower bounds for m(G,r) in general graphs and for graphs with special properties (random and pseudo-random graphs, graphs without short cycles) and discuss many unresolved questions. Based on joint work with Amin Coja-Oghlan, Uriel Feige and Michael Krivelevich. ---------------------------------- Next week: no talk (conflict with Barbados workshop). Week after: TBA Anyone wishing to be added to or removed from this mailing list should contact Paul Seymour (pds@math.princeton.edu)