Topology and Geometry of Crystallized Polyominoes

MaRDI QIDQ6327730zbMATH OpenFDO

Authors Greg Malen, Érika Roldán

Publication date 23 October 2019

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Asymptotic enumeration (05A16) Combinatorial inequalities (05A20) Polyominoes (05B50) Extremal combinatorics (05D99)

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.

This page was built for publication: Topology and Geometry of Crystallized Polyominoes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6327730)