***********************************
* 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)