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 (RAIRO: ITA), 54. 5. ISSN 1290-385X (https://doi.org/10.1051/ita/2020004)

[thumbnail of Chen-Kitaev-RAIRO-TIA-2020-On-universal-partial-words-for-word-patterns-and-set-partitions]
Preview
 Text. Filename: Chen_Kitaev_RAIRO_TIA_2020_On_universal_partial_words_for_word_patterns_and_set_partitions.pdf
Accepted Author Manuscript
Download (495kB)| Preview

Abstract

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.

CORE (COnnecting REpositories)