Bootstrap percolation via automated conjecturing

Abstract

Bootstrap percolation is a simple monotone cellular automaton with a long history in physics, computer science, and discrete mathematics. In k-neighbor bootstrap percolation, a collection of vertices are initially infected.  Vertices with at least k infected neighbors subsequently become infected; the process continues until stability is reached. In this paper, we hunt for graphs which can become entirely infected from initial sets which are as small as possible.  We use automated conjecture-generating software and a large group lab-based model as a fundamental part of our exploration.