On universal partial words for word-patterns and set partitions

Chen, Herman Z. Q. and Kitaev, Sergey (2020) On universal partial words for word-patterns and set partitions. RAIRO - Theoretical Informatics and Applications, 54. 5. ISSN 0988-3754

Text (Chen-Kitaev-RAIRO-TIA-2020-On-universal-partial-words-for-word-patterns-and-set-partitions)
Accepted Author Manuscript

Download (495kB)| Preview


    Universal words are words containing exactly once each element from a given set of combinatorial structures admiting encoding by words. Universal partial words (u-p-words) contain, in addition to the letters from the alphabet in question, any number of occurrences of a special ``joker'' symbol. We initiate the study of u-p-words for word-patterns (essentially, surjective functions) and (2-)set partitions by proving a number of existence/non-existence results and thus extending the results in the literature on u-p-words and u-p-cycles for words and permutations. We apply methods of graph theory and combinatorics on words to obtain our results.