Minimum Number of Holes in Unavoidable Sets

Partial words are sequences over a finite alphabet that may have some undefined positions called holes. A set X of partial words over an alphabet A is called unavoidable if every two-sided infinite word over A has a factor compatible with a member of X. In this paper, we consider unavoidable sets of partial words of uniform length over an alphabet of any fixed size. We investigate the minimum number of holes in such sets.

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