TILING WITH POLYOMINOES AND COMBINATORIAL GROUP-THEORY

When can a given finite region consisting of cells in a regular lattice (triangular, square, or hexagonal) in R2 be perfectly tiled by tiles drawn from a finite set of tile shapes? This paper gives necessary conditions for the existence of such tilings using boundary invariants, which are combinatorial group-theoretic invariants associated to the boundaries of the tile shapes and the regions to be tiled. Boundary invariants are used to solve problems concerning the tiling of triangular-shaped regions of hexagons in the hexagonal lattice with certain tiles consisting of three hexagons. Boundary invariants give stronger conditions for nonexistence of tilings than those obtainable by weighting or coloring arguments. This is shown by considering whether or not a region has a signed tiling, which is a placement of tiles assigned weights 1 or -1, such that all cells in the region are covered with total weight 1 and all cells outside with total weight 0. Any coloring (or weighting) argument that proves nonexistence of a tiling of a region also proves nonexistence of any signed tiling of the region as well. A partial converse holds: if a simply connected region has no signed tiling by simply connected tiles, then there is a generalized coloring argument proving that no signed tiling exists. There exist regions possessing a signed tiling which can be shown to have no perfect tiling using boundary invariants. © 1990.