2024/05/28 by Condon, D., Wang, Yuxin, Yang, E.
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2405.18543
We introduce the notions of de Bruijn polyominoes and prismatic polyominoes, which generalize the notions of de Bruijn sequences and arrays. Given a small fixed polyomino p and a set of colors [n], a de Bruijn polyomino for (p,n) is a colored fixed polyomino P with cells colored from [n] such that every possible coloring of p from [n] exists as a subset of P. We call de Bruijn polyominoes for (p,n) of minimum size (p,n)-prismatic. We discuss for some values of p and n the shape of a (p,n)-prismatic polyomino P, the construction of a coloring of P, and the enumeration of the colorings of P. We find evidence that the difficulty of these problems may depend on the parity of the size of p