Minimum Number of Holes in Unavoidable Sets

Partial words are sequences over a finite alphabet that may contain some undefined positions called holes. In this paper, we consider unavoidable sets of partial words of constant length. We investigate the minimum number of holes in sets of a fixed cardinality, as well as the minimum size of sets of words with a fixed number of holes.

Keywords: Combinatorics on words; Partial words; Unavoidable sets.