Locked Polyomino Tilings

A locked $t$-omino tiling is a grid tiling by $t$-ominoes such that, if you remove any pair of tiles, the only way to fill in the remaining space with $t$-ominoes is to use the same two tiles in the exact same configuration as before. We exclude degenerate cases where there is only one tiling overall due to small dimensions. Locked $t$-omino tilings arise as obstructions to widely used political redistricting algorithms in a grid model of redistricting. It is a classic (and straightforward) result that finite grids do not admit locked 2-omino tilings. In this paper, we construct explicit locked 3-, 4-, and 5-omino tilings of grids of various sizes. While 3-omino tilings are plentiful, 4- and 5-omino tilings are remarkably elusive. Using an exhaustive computational search, we completely enumerate all locked tilings on grid sizes up to $20 \times 20$, and all symmetric locked tilings on grid sizes up to $35 \times 35$. We find only a single 4-omino tiling (on the $10 \times 10$ grid) and a small handful of 5-omino tilings (only on $20 \times 20$ grids and larger). Finally, we construct a family of infinite periodic locked $t$-omino tilings with unbounded $t$ for both square and triangular grid lattices.