Extremal topological and geometric problems for polyominoes

Greg Malen¹ ; Erika Berenice Roldan-Roa²

¹Duke University
²The Ohio State University

The electronic journal of combinatorics, Tome 27 (2020) no. 2

Résumé

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.

Détail

DOI : 10.37236/9086

Classification : 05A15, 05A20, 05B50, 05D99, 57M15
Mots-clés : extremal topological properties, dual graph of a polyomino