On shortening universal words for multi-dimensional permutations

Kitaev, Sergey and Qiu, Dun (2026) On shortening universal words for multi-dimensional permutations. Discrete Mathematics, 349 (8). 115081. ISSN 0012-365X (https://doi.org/10.1016/j.disc.2026.115081)

Preview

Text. Filename: Kitaev-Qiu-DM-2026-On-shortening-universal-words-for-multi-dimentional.pdf Final Published Version License: Download (405kB)| Preview

Abstract

A universal word (u-word) for d-dimensional permutations of length nis a 2-dimensional word with d−1rows, any size nwindow of which is order-isomorphic to exactly one permutation of length n, and all permutations of length nare 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≤2d−1n−1[︄(1+(n−1)!)d−1−(︃1+(n−1)!2 )︃d−1]︄, for d-dimensional permutations of length nexist, which generalizes the respective result of Kitaev, Potapov and Vajnovszki for permutations (d=2).

ORCID iDs

Kitaev, Sergey ORCID: https://orcid.org/0000-0003-3324-1647

• Share and Export
  

  HTML CitationSimple MetadataMPEG-21 DIDLMultiline CSVData Cite XMLJSONOpenURL ContextObject in SpanMODSRDF+N3METSDublin CoreReferRefWorksOpenURL ContextObjectEP3 XMLRIS (EndNote Online, Zotero, Ref manager, etc)EndNoteASCII CitationRDF+N-TriplesRIOXX2 XMLRDF+XMLBibTeXAtom
• Item metadata

  Item type:	Article
  ID code:	95695
  Dates:	Date Event 1 August 2026 Published 5 March 2026 Published Online 28 February 2026 Accepted
  Subjects:	Science > Mathematics
  Department:	Faculty of Science > Mathematics and Statistics
  Depositing user:	Pure Administrator
  Date deposited:	03 Mar 2026 14:59
  Last modified:	11 Mar 2026 02:02
  URI:	https://strathprints.strath.ac.uk/id/eprint/95695