Topology and Geometry of Crystallized Polyominoes

2019/10/23 by Malen, Greg, Roldán, Érika
#05A15 #05A16 #05A20 #05B50 #05D99 #Algebraic Topology (math.AT) #Combinatorics (math.CO) #FOS: Mathematics #Geometric Topology (math.GT) #and 57M20

paper · doi:10.48550/arxiv.1910.10342

Abstract

We give a complete solution to the extremal topological combinatorial problem of finding the minimum number of tiles needed to construct a polyomino with h holes. We denote this number by g(h) and say that a polyomino is crystallized if it has h holes and g(h) tiles. We analyze structural properties of crystallized polyominoes and characterize their efficiency by a topological isoperimetric inequality that relates minimum perimeter, the area of the holes, and the structure of the dual graph of a polyomino. We also develop a new dynamical method of creating sequences of polyominoes which is invariant with respect to crystallization and efficient structure. Using this technique, we prove that crystallized polyominoes with h_l=(2^2l-1)/3 holes are unique.

Related

• Polyiamonds Attaining Extremal Topological Properties, Part II
• Polyominoes with maximally many holes
• Tiling rectangles with holey polyominoes
• Signed polyomino tilings by n-in-line polyominoes and Groebner bases
• Tiling with Squares and Packing Dominos in Polynomial Time