Combinatorics For General Kinetically Constrained Spin Models

We study the set of possible configurations for a general kinetically constrained model (KCM), a nonmonotone version of the U-bootstrap percolation cellular automata. We solve a combinatorial question that, is a generalization of a problem addressed by Chung, Diaconis, and Graham [Adv. in Appl. Math., 27 (2001), pp. 192-206] for a specific one-dimensional KCM, the East model. Since the general models we consider are in any dimension and lack the oriented character of the East dynamics, we have to follow a completely different route than the one taken by Chung, Diaconis, and Graham. Our combinatorial result is used by Mareche, Martinelli, and Toninelli to complete the proof of a conjecture put forward by Morris.