◊ Minimal Cardinality of Unavoidable Sets ◊

In the context of full words, the minimal cardinality of unavoidable sets of words of a given length m over a k-letter alphabet has been shown to be precisely equal to c(m,k), the number of conjugacy classes of words of that length over the given alphabet. We examine the case of partial words of length m with h holes over a k-letter alphabet and attempt to find bounds for the minimal cardinality of such unavoidable sets.

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