On shortening u-cycles and u-words for permutations

2017/07/19 by Kitaev, Sergey, Potapov, Vladimir N., Vajnovszki, Vincent
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1707.06110

Abstract

This paper initiates the study of shortening universal cycles (u-cycles) and universal words (u-words) for permutations either by using incomparable elements, or by using non-deterministic symbols. The latter approach is similar in nature to the recent relevant studies for the de Bruijn sequences. A particular result we obtain in this paper is that u-words for n-permutations exist of lengths n!+(1-k)(n-1) for k=0,1,…,(n-2)!.

Related

• Universal cycles for permutations
• Universal Cycles of Complementary Classes
• On the probability of existence of a universal cycle or a universal word for a set of words
• On a family of universal cycles for multi-dimensional permutations
• Overlap Cycles for Permutations: Necessary and Sufficient Conditions