Neal Bushaw (Virginia Commonwealth University) - Small Percolating Sets

Nov 4, 4:00, Votey 207

Bootstrap percolation is a simple monotone cellular automaton which was originally introduced by Chalupa, Leath and Reich as a model of ferromagnetism in the late 1970s. The model is most easily described as an infection process: we think of some vertices as becoming infected by a mystery disease called Graphitis.  Even worse, Graphitis is contagious -- if a healthy vertex is exposed to Graphitis by a large number of its neighbors, then the healthy vertex gets sick. There is an enormous pile of interesting questions here: Does the infection spread to the entire graph?  Will it stop?  Is there a way to quarantine Graphitis?

In this talk, we give an introduction to bootstrap percolation and its history, highlighting a few major breakthroughs and classic problems. Then, we'll proceed to a deceptively simple sounding extremal problem -- which graphs are the most susceptible to infection?

This question was the topic of a somewhat unusual working group called the Graph Brain Project, where a combination of faculty, graduate students, undergraduates, and high school students worked together with automated conjecturing software in order to explore this question.  We will describe several results which came out of the summer's work, as well as an in-depth discussion of the automated conjecturing paradigm.

No background knowledge will be assumed -- the aim of this talk is to introduce you to bootstrap percolation and its plethora of fascinating open problems, rather than to show complicated proofs.