  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 $2t$ grid cells
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. It is a classic (and straightforward) result that
finite grids do not admit locked 2-omino tilings. In this paper, we construct
explicit locked $t$-omino tilings for $t \geq 3$ on grids of various
dimensions. Most notably, we show that locked 3- and 4-omino tilings exist on
finite square grids of arbitrarily large size, and locked $t$-omino tilings of
the infinite grid exist for arbitrarily large $t$. The result for 4-omino
tilings in particular is remarkable because they are so rare and difficult to
construct: Only a single tiling is known to exist on any grid up to size $40
\times 40$.
  Locked $t$-omino tilings arise as obstructions to widely used political
redistricting algorithms in a model of redistricting where the underlying
census geography is a grid graph. Most prominent is the ReCom Markov chain,
which takes a random walk on the space of redistricting plans by iteratively
merging and splitting pairs of districts (tiles) at a time. Locked $t$-omino
tilings are isolated states in the state space of ReCom. The constructions in
this paper are counterexamples to the meta-conjecture that ReCom is irreducible
on graphs of practical interest.
