Topology and Geometry of Crystallized Polyominoes

arXiv1910.10342MaRDI QIDQ6327730FDOQ6327730

Authors: Greg Malen, Érika Roldán 

Publication date: 23 October 2019

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.

Mathematics Subject Classification ID

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

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)