Bootstrap percolation via automated conjecturing

Neal Bushaw, Craig Larson


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.


Percolation, bootstrap percolation, minimal percolating sets, extremal, automated conjecturing

Full Text:



ISSN: 1855-3974

Issues from Vol 6, No 1 onward are partially supported by the Slovenian Research Agency from the Call for co-financing of scientific periodical publications