Extremal topological and geometric problems for polyominoes


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\leq 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\‘oldan-Roa in 2019, who also showed that asymptotically $g(h) \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(h_l)$ tiles are in fact unique up to isometry with these fixed parameters; that is, having the minimal number of tiles for $h_l$ holes.

The Electronic Journal of Combinatorics