Bootstrap percolation via automated conjecturing

Neal Bushaw, Craig Larson

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.

Keywords


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

Full Text:

MANUSCRIPT


DOI: https://doi.org/10.26493/1855-3974.2340.a61

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