Extremal topological and geometric problems for polyominoes
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.
- High-dimensional holeyominoes
- Extremal \(\{ p, q\}\)-animals
- Polyiamonds attaining extremal topological properties. II.
- Polyiamonds attaining extremal topological properties. I
- Polyominoes with maximally many holes
- scientific article; zbMATH DE number 6468924 (Why is no real title available?)
- An extremal graph problem on a grid and an isoperimetric problem for polyominoes
- Maximum area converses of Harary-Harborth polyform theorems
- Adding layers to bumped-body polyforms with minimum perimeter preserves minimum perim\-eter
This page was built for publication: Extremal topological and geometric problems for polyominoes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q782931)
