Extremal Topological and Geometric Problems for Polyominoes

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 we analyze structural properties of polyominoes with $h$ holes and $g(h)$ tiles, characterizing 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. For $h\leqslant 8$ the values of $g(h)$ were originally computed by Tomas Olivera e Silva in 2015, and for the sequence $h_l=(2^{2l}-1)/3$ by Kahle and Róldan-Roa in 2019, who also showed that asymptotically $g(h) \approx 2h$. Here we also prove that the sequence of polyominoes constructed by Kahle and Róldan-Roa that have $h_l=(2^{2l}-1)/3$ holes and $g(h_l)$ tiles, are in fact unique up to isometry with respect to attaining these extremal topological properties; that is, having the minimal number of tiles for $h_l$ holes.