Lower bounds for graph bootstrap percolation via properties of polynomials

Abstract We introduce a simple method for proving lower bounds for the size of the smallest percolating set in a certain graph bootstrap process. We apply this method to obtain recursive formulas for the sizes of the smallest percolating sets in multidimensional tori and multidimensional grids (in particular hypercubes). The former answers a question of Morrison and Noel [9] , and the latter provides an alternative and simpler proof for one of their main results.