[Theory Seminar] Daniel Reichman

When:
April 17, 2019 @ 12:00 pm – 1:00 pm
2019-04-17T12:00:00-04:00
2019-04-17T13:00:00-04:00

Speaker: Daniel Reichman
Affiliation: Princeton University

Title: Contagious sets in bootstrap percolation

Abstract:
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.