Extremal topological and geometric problems for polyominoes (Q782931)

Summary: 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 \textit{T. Olivera e Silva} [``Animal enumerations on the \(\{4,4\}\) Euclidian tiling'', Preprint, \url{http://sweet.ua.pt/tos/animals/a44.html}], and for the sequence \(h_l=(2^{2l}-1)/3\) by \textit{M. Kahle} and \textit{É. Roldán} [Geombinatorics 29, No. 1, 5--20 (2019; Zbl 1428.05052)], who also showed that asymptotically \(g(h) \approx 2h\). Here we also prove that the sequence of polyominoes constructed by Kahle and Róldan [loc. cit.] 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.