Construction of small superpermutations and minimal injective superstrings. (English) Zbl 0801.05004

Summary: A superpermutation is a string over an alphabet \(\mathcal A\) that contains every permutation of the elements of \(\mathcal A\) as a contiguous substring. In this paper, we present a recursive construction for a very small superpermutation on the alphabet \({\mathcal A}= \{1,2,\dots,n\}\). We also treat the case where every string of length \(k< n\) with no repeated characters is to appear as a contiguous substring. Such a string is called an injective superstring on strings of length \(k\) over \(\mathcal A\).


05A05 Permutations, words, matrices
05C99 Graph theory
68R15 Combinatorics on words
05C20 Directed graphs (digraphs), tournaments