A cube dismantling problem related to bootstrap percolation

An n×n×n cube is made from n³ unit cubes. Two such cubes are neighbours if they touch along a face. In each step of a dismantling process, we may remove a small cube that has precisely three neighbours. A move is balanced if the three neighbours are in three orthogonal directions. In the extremal case, there are n² independent small cubes left at the end of the dismantling. We call these cubes a solution. If a solution is projected in three orthogonal directions and we get the entire n×n square in each direction, then we say we have a perfect solution.

We show that it is possible to use a greedy algorithm to test whether a set of cubes forms a solution. For every n≥2 we find at least n perfect solutions, and we use our greedy algorithm to count the perfect solutions for n≤6. Perfect solutions turn out to be precisely those which can be reached using only balanced moves. Every perfect solution corresponds naturally to a Latin square. However, we show that almost all Latin squares do not correspond to solutions.

We construct an infinite family of imperfect solutions and show that the total size of its three orthogonal projections is asymptotic to the minimum possible value.

Our results solve several conjectures posed in a proceedings paper by Barát, Korondi and Varga.

If our dismantling process is reversed we get a build-up process very similar to well-studied models of bootstrap percolation.