×

On universal partial words for word-patterns and set partitions. (English) Zbl 1460.68079

Universal words are words containing exactly once each element from a given set of combinatorial structures admitting encoding by words. F. Chung et al. [Discrete Math. 110, No. 1–3, 43–59 (1992; Zbl 0776.05001)] introduced the notion of a universal cycle, or u-cycle, for any class of combinatorial objects that admits encoding by words. A u-cycle is a cyclic word containing each encoded object of fixed size exactly once as a factor. 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. In this paper the authors study u-p-words for word-patterns 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. One of the most significant ideas introduced is the usage of context-dependent \(\star\)s in the context of u-p-words, which can be seen as a brother of the restricted \(\star\)s studied in the context of permutations.

MSC:

68R15 Combinatorics on words
05A05 Permutations, words, matrices
05A18 Partitions of sets
05C38 Paths and cycles

Citations:

Zbl 0776.05001
PDFBibTeX XMLCite
Full Text: DOI Link

References:

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.