Paper Info
Title
Tiling with Polyominoes and Combinatorial Group Theory
Abstract
When can a given finite region consisting of cells in a regular lattice (triangular, square, or hexagonal) in R 2 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.
Year
DOI
Venue
1990
10.1016/0097-3165(90)90057-4
J. Comb. Theory, Ser. A
Keywords
Field
DocType
combinatorial group theory
Discrete mathematics,Rhombille tiling,Combinatorics,Square tiling,Substitution tiling,Trihexagonal tiling,Hexagonal tiling,Arrangement of lines,Triangular tiling,Tessellation,Mathematics
Journal
Volume
Issue
ISSN
53
2
Journal of Combinatorial Theory, Series A
Citations 
PageRank 
References 
60
17.40
0
Authors
2
Name
Order
Citations
PageRank
J. H. Conway134868.80
J. C. Lagarias2563235.61