Polyominoes with maximally many holes

Abstract

What is the maximum number of holes that a polyomino with $n$ tiles can enclose? Call this number $f(n)$. We show that if $n_k=\left(2^{2k+1}+3\cdot 2^{k+1}+4\right)/3$ and $h_k=\left(2^{2k}-1\right)/3$, then $f(n_k)=h_k$ for $k\ge 1$. We also give nearly matching upper and lower bounds for large $n$, showing as a corollary that $f(n)\approx n/2$.

16 pages, 10 figures, 1 table