On shortening universal words for multi-dimensional permutations

Abstract

A universal word (u-word) for $d$-dimensional permutations of length $n$ is a 2-dimensional word with $d-1$ rows, any size $n$ window of which is order-isomorphic to exactly one permutation of length $n$, and all permutations of length $n$ are covered. It is known that u-words (in fact, even u-cycles, a stronger claim) for $d$-dimensional permutations exist. In this paper, we use the idea of incomparable elements to prove that u-words of length $(n!{)}^{d-1}+n-1-i(n-1)$, for $d\ge 2$ and $$0\le i\le \frac{2^{d-1}}{n-1}\left[(1+(n-1)!{)}^{d-1}-{\left(1+\frac{(n-1)!}{2}\right)}^{d-1}\right],$$ for $d$-dimensional permutations of length $n$ exist, which generalizes the respective result of Kitaev, Potapov and Vajnovszki for ``usual'' permutations ($d=2$).

To appear in Discrete Mathematics