Polyomino Tilings: from combinatorics to topology

Abstract

A polyomino is a plane geometric gure formed by joining one or more equal squares edge to edge. The problem of tiling a region in a plane or a surface with square grid by the given set of polyomino shapes and questions of di erent number of tilings have been extensively studied in combinatorics. We introduce a simplicial complex related to the problem and it turns out that its combinatorics and topology have many interesting properties. For example, a face vector of a such complex reveals the number of di erent placements of a certain shapes on the region without overlapping. This large group of simplicial complexes fails in general to be Cohen-Macaulay, but in many cases they still have the homotopy type of a wedge of spheres. Morover, they can be considered as a natural generalization of the matching complex of a graph on a square grid which are studied a lot in the last years. Combinatorial, topological and algebraic properties of polyomino tilings complexes provide many interesting and nice applications we are going to talk about.