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 ≥ 2 and 0 ≤ i ≤ 2 d − 1 n − 1 [ ( 1 + ( n − 1 ) ! ) d − 1 − ( 1 + ( n − 1 ) ! 2 ) d − 1 ] , for d -dimensional permutations of length n exist, which generalizes the respective result of Kitaev, Potapov and Vajnovszki for “usual” permutations ( d = 2 ).
Fields of Study & Subjects
Advanced Combinatorial Mathematics
semigroups and automata theory
Algorithms and Data Compression
Publication details
- Journal / source
- Discrete Mathematics
- Volume
- 349
- Issue
- 8
- Pages
- 115081–115081
- Publication date
- 5 March 2026
- Language
- EN