On universal partial words for word-patterns and set partitions

¹ School of Statistics and Data Science, Nankai University, PR China.
² Department of Mathematics and Statistics, University of Strathclyde, UK.

^* Corresponding author: zqchern@nankai.edu.cn

Received: 28 February 2019
Accepted: 10 March 2020

Abstract

Universal words are words containing exactly once each element from a given set of combinatorial structures admitting 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.