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