Polyominoes with maximally many holes

2018/07/26 by Kahle, Matthew, Roldán, Érika
#05B50 #05Dxx #Algebraic Topology (math.AT) #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1807.10231

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 = ( 2^2k+1 + 3 ⋅ 2^k+1+4 ) / 3 and h_k = ( 2^2k-1 ) /3, then f(n_k) = h_k for k ≥ 1. We also give nearly matching upper and lower bounds for large n, showing as a corollary that f(n) ≈ n/2.

Related

• Topology and Geometry of Crystallized Polyominoes
• Largest polyomino with no four cells equally spaced on a straight line
• The Number of Convex Polyominoes with Given Height and Width
• Tiling rectangles with holey polyominoes
• Tiling with Squares and Packing Dominos in Polynomial Time